akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-12, PI = acos(-1);
const int N = 1e6 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

vector<pair<ll, ll>> vec;

ll tree[5*N], lazy[5*N];

void propagate(ll node, ll start, ll end) {
  if(!lazy[node])
    return;
  tree[node] += (lazy[node]) * (ll)(end - start + 1);
  if(start != end) {
    lazy[node * 2] += lazy[node];
    lazy[node * 2 + 1] += lazy[node];
  }
  lazy[node] = 0;
}

ll query(ll node, ll start, ll end, ll idx) {
  propagate(node, start, end);
  if(start == end)
    return tree[node];
  ll mid = (start + end) / 2;
  if(idx <= mid)
    return query(node * 2, start, mid, idx);
  else
    return query(node * 2 + 1, mid + 1, end, idx);
}

void update(ll node, ll start, ll end, ll l, ll r, ll val) {
  propagate(node, start, end);
  if(start > r || end < l)
    return;
  if(start >= l && end <= r) {
    lazy[node] = val;
    propagate(node, start, end);
    return;
  }
  ll mid = (start + end) / 2;
  update(node * 2, start, mid, l, r, val);
  update(node * 2 + 1, mid + 1, end, l, r, val);
  tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  ll n, D, A;
  cin >> n >> D >> A;
  map<ll, ll> mp;
  ll x, h;
  for (int i = 0; i < n; ++i) {
    cin >> x >> h;
    vec.push_back({x, h});
    mp[x];
//    mp[x + D];
    ll endPoint = x + (2ll * D);
    mp[endPoint];
  }
  int idx = 1;
  for(auto it: mp)
    mp[it.first] = idx++;
  sort(vec.begin(), vec.end());
  for (int i = 0; i < n; ++i) {
    update(1, 1, idx, mp[vec[i].first], mp[vec[i].first], vec[i].second);
  }
  ll total = 0;
  for (int i = 0; i < n; ++i) {
    ll vvo = query(1, 1, idx, mp[vec[i].first]);
    if(vvo > 0) { // lw ana > 0
      ll startPoint = mp[vec[i].first];
      ll endPoint = vec[i].first + (2ll * D);
      endPoint = mp[endPoint];
      ll kam = (vvo / A) + (vvo % A != 0);
      total += kam;
      kam *= A;
      kam *= -1;
      update(1, 1, idx, startPoint, endPoint, kam);
    }
  }
  cout << total;
  return 0;
}


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

int main() {
  int a,b;
  double A,B;
  cin >> a >> b;
  A = a;
  B = b;
  cout << ((a + b) / 2) + (((A + B)/ 2) - ((a + b) / 2)) * 2 << endl;
}


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

int main(){
    string a,b;
    cin >> a >> b;
    if(a[0]==b[2] && a[1]==b[1] && a[2]==b[0]){
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;
}

Measured memory_bytes: 256
def solution
  s = gets.chomp
  size = s.size
  expressions = []
  [' ', '+'].repeated_permutation(size - 1).each do |c|
    expression = ''
    (size).times do |i|
      expression << s[i]
      expression << c[i] if c[i]
    end
    expressions << expression.gsub(' ', '')
  end
  answer = 0
  expressions.each do |expression|
    answer = answer + expression.split('+').map(&:to_i).inject(:+)
  end
  answer
end

puts solution


Measured memory_bytes: 1916
#include <bits/stdc++.h>
using namespace std;
#define _                             \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL);
#define deb(x) cerr << "\n" \
					<< #x << "=" << x << "\n";
#define deb2(x, y) cerr << "\n"                   \
						<< #x << "=" << x << "\n" \
						<< #y << "=" << y << "\n";
typedef long long int ll;

const ll mod = 1e9 + 7;

ll n;
vector<vector<ll>> v;
vector<vector<ll>> dp;
ll ans;
// 0 -> black , 1->white

ll go(ll x, ll parent, ll parent_color)
{
	ll white = 1;
	ll black = 1;

	if (dp[parent_color][x] != -1)
		return dp[parent_color][x];

	if (parent_color == 0)
		black = 0;

	for (ll i : v[x])
	{
		if (i == parent)
			continue;

		white = (white % mod * go(i, x, 1) % mod) % mod;

		if (parent_color != 0)
		{
			black = (black % mod * go(i, x, 0) % mod) % mod;
		}
	}
	dp[parent_color][x] = (black % mod + white % mod) % mod;
	return dp[parent_color][x];
}

int main()
{

	cin >> n;
	v.resize(n + 1);
	dp.resize(2, vector<ll>(n + 1, -1));
	for (ll i = 0; i < n - 1; i++)
	{
		ll foo1, foo2;
		cin >> foo1 >> foo2;
		v[foo1].push_back(foo2);
		v[foo2].push_back(foo1);
	}

	cout << go(1, -1, 1);

	//cout << ans;
}


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MAXN 100001


int main() {
    int n;
    int h[MAXN];

    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> h[i];
    }

    ll cost[MAXN];
    cost[0] = 0;
    cost[1] = abs(h[1] - h[0]);

    for(int i=2; i<n; i++) {
        cost[i] = min(cost[i-2] + abs(h[i] - h[i-2]), cost[i-1] + abs(h[i] - h[i-1]));
//        cout << cost[i] << endl;
    }

    cout << cost[n-1] << endl;

    
}



Measured memory_bytes: 1408
import java.util.*;

class Main{
  
  public static void main(String [] args)
  {
 		Scanner sc  = new Scanner(System.in);
    	String F =sc.nextLine();
    	String C =sc.nextLine();
    	int count=0;
    	for(int i=0;i<F.length();i++)
        {
          Character c1 = F.charAt(i);
          Character c2 = C.charAt(i);
          
          if(c1==c2) count++;
        }
    
    System.out.println( count);
  }
  
}

Measured memory_bytes: 22868
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = [0 for i in range(N+1)]
ans = 0
tmp = set()
tmp.add(0)
for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = 1 + dp[i-k]
            tmp.add(i)
            break


num.sort(reverse=True)
tmp = N
ans = []
for i in reversed(range(1, dp[N])):
    for n, k in num:
        if dp[tmp - k] == i:
            ans.append(n)
            tmp -= k
            break
for n, k in num:
    if k == tmp:
        ans.append(n)
        break

ans.sort(reverse=True)
ans = "".join(map(str, ans))
print(ans)


Measured memory_bytes: 4208
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int m,n, a[1005]; 
int main(){
	cin>>n>>m;
	int sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	
	int target=ceil(sum*1.0/4/m);
	
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>=target) cnt++;
	}
	if(cnt>=m)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;


public class Main{
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		long a, b;
		while(sc.hasNext()) {
			a = sc.nextLong();
			b = sc.nextLong();
			System.out.println(LCM(a, b) + " " + GCD(a, b));
		}
		sc.close();
	}
	
	static long GCD(long a, long b) {
		return a * b / LCM(a, b);
	}
	
	static long LCM(long a, long b) {
		long n0 = (a >= b) ? a: b;
		long n1 = (a >= b) ? b: a;
		
		if(n1 == 0) return n0;
		else return LCM(n1, n0 % n1);
	}
}

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

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    if (n > m) {
        swap(n, m);
    }

    if (n == 1) {
        if (m == 1) {
            printf("%d\n", 1);
        } else {
            printf("%d\n", m - 2);
        }
    } else {
        printf("%lld\n", (long long)(n - 2) * (m - 2));
    }
    return 0;
}

Measured memory_bytes: 256
/*---------------------------------

 @Author:   Dicer
 @DateTime: 2019-05-28 19:49:36

---------------------------------*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const int MAXN = 2e5 + 7;

int s[23][23], p[23], c[23];
int main(int argc, char const *argv[])
{
	int ans = 0;
	int n, m, k, x;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		cin >> k;
		for(int j = 1; j <= k; ++j){
			cin >> x;
			s[i][x] = 1;
		}
	}
	for(int i = 1; i <= m; ++i)	cin >> p[i];
	for(int i = 0; i < (1<<n); ++i){
		for(int j = 1; j <= m; ++j)	c[j] = 0;
		for(int j = 0; j < n; ++j){
			if((i>>j)&1){
				for(int k = 1; k <= m; ++k){
					if(s[k][j+1]){
						c[k]++;
						c[k] %= 2;
					}
				}
			}
		}
		int cnt = 0;
		for(int j = 1; j <= m; ++j){
			if(c[j] == p[j])	cnt++;
		}
		if(cnt == m)	ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <math.h>
#include <random>
#include <chrono>
#include <assert.h>
#include <ctime>
#include <bitset>

using namespace std;

#define x first
#define y second
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define SZ(x) int(x.size())
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b-1; i >= a; i--)
#define DBG(x) cerr << (#x) << "=" << x << "\n";
#define ll long long
#define inf 1000000007
#define mod 99824353 //1000000007
#define N 501

template<typename U, typename V> void Min(U &a, const V & b){if(a > b)a = b;}
template<typename U, typename V> void Max(U &a, const V & b){if(a < b)a = b;}
template<typename U, typename V> void add(U &a, const V & b){a = (a + b) % mod;}
template<typename U> U gcd(U a, U b){
    if(a == 0)return b;
    if(b == 0)return a;
    if(a >= b)return gcd(a % b, b);
    else return gcd(a, b % a);
}
int pow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)ans = 1LL * ans * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int pow(int a, ll b, int c){
    int ans = 1;
    while(b){
        if(b & 1)ans = 1LL * ans * a % c;
        a = 1LL * a * a % c;
        b >>= 1;
    }
    return ans;
}

int p[N * N], vis[N][N], dp[N][N]; 
priority_queue<pair<int, pii>> q;
void Push(int x, int y, int w){
  if (dp[x][y] > w){
    dp[x][y] = w;
    q.push({-w, {x, y}});
  }
}
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
int main() {
  int ca = 0, T, i, j, k, m, K, n;
  scanf("%d", &n);
  m = n * n;
  rep(i, 0, m){
    scanf("%d", &p[i]);
    p[i]--;
  }
  rep(i, 0, n){
    rep(j, 0, n){
      dp[i][j] = min(min(i, n-1-i), min(j, n-1-j));
      vis[i][j] = 0;
    }
  }
  int ans = 0, w;
  rep(i, 0, m){
    int x = p[i]/n, y = p[i]%n;
    w = dp[x][y];
    ans += dp[x][y];
    q.push({-w, {x, y}});
    vis[x][y] = 1;
    while(!q.empty()) {
      w = -q.top().x;
      x = q.top().y.x, y = q.top().y.y;
      q.pop();
      rep(j, 0, 4){
        int nx = x + dx[j], ny = y + dy[j];
        if(nx >= 0 && nx < n && ny >= 0 && ny < n){
          int nw = w + (!vis[x][y]);
          Push(nx, ny, nw);
        }
      }
    }
  }
  printf("%d\n", ans);
}


Measured memory_bytes: 6832
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;

const int INF = 0x7f7f7f7f;
const int MAXN = 1e5 + 10;
int a[MAXN];
int N, K;
int id;
int res = INF;

int AAA(int x) {
	if(x % K == 0)
		return x / K;
	else return x / K + 1;
}

int main() {
	scanf("%d%d", &N, &K);
	for(int i = 1; i <= N; ++i) {
		scanf("%d", a + i);
		if(a[i] == 1) id = i;
	}
	/*for(int j = 0; j < K; ++j) {
		int s = K - j - 1;
		int l = id - s, r = id + j;
		cout<<l<<" "<<r<<endl;
		if(l < 1) continue;
		if(r > N) break;
		res = min(res, AAA(l) + AAA(N - r + 1));
	}*/
	int now = 1, cnt = 0;
	while(now <= N){ 
		now += K - 1;
		
		cnt++;
		if(now == N) break;
	}
	cout<<cnt;
	return 0;
}

Measured memory_bytes: 640
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  private void solve(Scanner in, PrintWriter out) {
    int V = in.nextInt();
    int E = in.nextInt();
    PushRelabel relabel = new PushRelabel(V);
    for (int i = 0; i < E; i++) {
      int u = in.nextInt();
      int v = in.nextInt();
      int c = in.nextInt();
      relabel.addEdge(u, v, c);
    }
    out.println(relabel.maxFlow(0, V - 1));
  }
  class PushRelabel {
    class Edge {
      int from, to, cap, flow, rev;
      Edge(int from, int to, int cap, int flow, int rev) {
        this.from = from;
        this.to = to;
        this.cap = cap;
        this.flow = flow;
        this.rev = rev;
      }
    }

    int N;
    ArrayList<ArrayList<Edge>> G = new ArrayList<>();
    long[] excess;
    int[] dist, count;
    boolean[] active;
    ArrayDeque<Integer> Q = new ArrayDeque<>();

    PushRelabel(int N) {
      this.N = N;
      for (int i = 0; i < N; i++) G.add(new ArrayList<>());
      excess = new long[N];
      dist = new int[N];
      active = new boolean[N];
      count = new int[N * 2];
    }

    void Push(Edge e) {
      int amt = (int) Math.min(excess[e.from], e.cap - e.flow);
      if (dist[e.from] <= dist[e.to] || amt == 0)
        return;
      e.flow += amt;
      G.get(e.to).get(e.rev).flow -= amt;
      excess[e.to] += amt;
      excess[e.from] -= amt;
      Enqueue(e.to);
    }

    void addEdge(int from, int to, int cap) {
      G.get(from).add(new Edge(from, to, cap, 0, G.get(to).size()));
      G.get(to).add(new Edge(to, from, 0, 0, G.get(from).size() - 1));
    }

    void Discharge(int v) {
      for (Edge e : G.get(v)) {
        if (excess[v] <= 0) break;
        Push(e);
      }
      if (excess[v] > 0) {
        if (count[dist[v]] == 1)
          Gap(dist[v]);
        else
          Relabel(v);
      }
    }

    void Enqueue(int v) {
      if (!active[v] && excess[v] > 0) {
        active[v] = true;
        Q.push(v);
      }
    }

    void Gap(int k) {
      for (int v = 0; v < N; v++) {
        if (dist[v] < k)
          continue;
        count[dist[v]]--;
        dist[v] = Math.max(dist[v], N + 1);
        count[dist[v]]++;
        Enqueue(v);
      }
    }

    void Relabel(int v) {
      count[dist[v]]--;
      dist[v] = 2 * N;
      for (Edge e : G.get(v))
        if (e.cap - e.flow > 0)
          dist[v] = Math.min(dist[v], dist[e.to] + 1);
      count[dist[v]]++;
      Enqueue(v);
    }

    long maxFlow(int s, int t) {
      count[0] = N - 1;
      count[N] = 1;
      dist[s] = N;
      active[s] = active[t] = true;
      for (Edge e : G.get(s)) {
        excess[s] += e.cap;
        Push(e);
      }

      while (!Q.isEmpty()) {
        int v = Q.poll();
        active[v] = false;
        Discharge(v);
      }

      long flow = 0;
      for (Edge e : G.get(s)) flow += e.flow;
      return flow;
    }

  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(in, out);
    in.close();
    out.close();
  }
}

Measured memory_bytes: 35556
def solve():
    p = int(input())
    *A, = map(int, input().split())

    L = p-1
    fact = [1]*(L+1)
    rfact = [1]*(L+1)
    r = 1
    for i in range(1, L+1):
        fact[i] = r = r * i % p
    rfact[L] = r = pow(r, p-2, p)
    for i in range(L, 0, -1):
        rfact[i-1] = r = r * i % p
    V = [(-fact[p-1] * rfact[k] * rfact[p-1-k]) % p for k in range(p)]

    B = [-i for i in range(p)]
    R = [0]*p
    I = [i for i, a in enumerate(A) if a]
    C = [a for a in A]

    for k in range(p):
        r = 0
        R[k] = V[k] * sum(C) % p

        for i in I:
            C[i] = C[i] * B[i] % p
    R[-1] += len(I)
    for k in range(p):
        R[k] %= p
    R.reverse()
    print(*R)
solve()

Measured memory_bytes: 4192
#include "bits/stdc++.h"
#include "math.h"
#include "string.h"
#include "algorithm"
 
using namespace std;
typedef int64_t ll;
typedef vector<int64_t> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SIZE(a) int((a).size())
const int INF=INT_MAX;

vll PrimeFactorization(int x){
  vll p(x+1,0);
  int a=2;
  while(x>1){
    if(x%a==0){
      x/=a;
      p[a]++;
    }
    else{
      a++;
    }
  }
  return p;
}
int main(){
  int n,m;
  cin>>n>>m;
  vll a=PrimeFactorization(n),b=PrimeFactorization(m);
  vll c(min(n,m)+1);
  REP(i,min(n,m)+1){
    c[i]=min(a[i],b[i]);
    a[i]-=c[i];
    b[i]-=c[i];
  }
  ll ans=1;
  FOR(i,2,max(m,n)+1){
    if(i<n+1){ans*=pow(i,a[i]);}
    if(i<m+1){ans*=pow(i,b[i]);}
    if(i<min(n,m)+1){ans*=pow(i,c[i]);}
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 2560
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{int N; cin >> N;
int min_cnt = N;
 for(int i = 0; i <= N; i++)
 {int s = i;
  int t = N - i;
  int a = 0; int b = 0;
  while(s > 0){ a += s % 6;
               s /= 6;}
  while(t > 0){ b += t % 9;
               t /= 9;}
   min_cnt = min( min_cnt, a+b);
 }
 
 cout << min_cnt << endl;
 
 return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include<stdio.h>
#include <climits>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	int n,i=1,j;
	int stac=0,old=0;
	int ans=0;
	int h[100001];


	cin >>n;
	while (cin >> h[i]) {
		i++;
	}
	h[i]=INT_MAX;

	for (i = 1; i <= n; i++) {
		j = i;
		while (h[j] >= h[j + 1]) {
			if (old == 0) {
				stac++;
				j++;
			}
			else {
				stac = stac -1 + old;
				j = j -1 + old;
				old = 0;
			}
		}
		old = stac;
		if (ans < stac)ans = stac;
		stac = 0;
	}

	cout << ans << "\n";
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  if (a%2 == 1 && b%2 == 1){
    cout << "Odd" << endl;
  }
  else cout << "Even" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void){
    char x[300];
    int lt,hf,i,fg;
    scanf("%s",&x);
    lt=strlen(x);
    lt-=2;
    while(1){
        hf=lt/2;
        fg=1;
        for(i=0;i+hf<lt;i++){
            if(x[i]!=x[i+hf]){
                fg=0;
                break;
            }
        }
        if(fg==1){
            break;
        }
        lt-=2;
    }
    printf("%d\n",lt);
    return 0;
}



Measured memory_bytes: 128
n = int(input())
a = list(map(int,input().split()))
q = int(input())
bc = []
# 現れる値の最大値を記録する
mx = max(a)
for i in range(q):
    bc.append(list(map(int,input().split())))
    mx = max(mx,max(bc[i][0],bc[i][1]))
# aの値をindexとするリストを作成する
a_count = [0 for i in range(mx+1)]
for x in a:
    a_count[x] += 1
# aの要素の和を求める
ans = sum(a)
for i in range(q):
    b,c = bc[i]
    # 操作後の値の変化量を計算する
    ans += (c - b) * a_count[b]
    # 操作後の要素の個数を変更する
    a_count[c] += a_count[b]
    a_count[b] = 0
    print(ans)

Measured memory_bytes: 32996
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
ll max(ll a, ll b){
    return a > b? a: b;
}
int dfs(vector< vector<int> > &g, vector<int> &dp, int ind) {
    if(dp[ind] != -1)
        return dp[ind];
    int h = -1;
    for(auto v: g[ind]) {
        h = max(h, dfs(g, dp, v));
    }
    dp[ind] = h+1;
    return dp[ind];
}
int main() {
    int n, m;
    cin >> n >> m;
    vector< vector<int> > g(n);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u-1].push_back(v-1);
    }
    vector<int> dp(n, -1);
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans = max(ans, dfs(g, dp, i));
    cout << ans << endl;
}


Measured memory_bytes: 8832
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n-1;i>=0;i--)

typedef long long ll;
#define INF 1e18

int main(){
	ll N;
	cin>>N;
	vector<ll> A(N);
	REP(i,N){
		cin>>A[i];
	}
	ll lsum=0,rsum=0;
	ll l=0,r=N-1;
	while(l<=r){
		if(lsum<rsum){
			lsum+=A[l];
			l++;
		}else{
			rsum+=A[r];
			r--;
		}
	}
	cout<<(lsum-rsum>0 ? lsum-rsum : rsum-lsum)<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int N,M;
bool e_flg=false;
// vector<vector<int> > ED;

// void dfs(int n, int c){
//     if(e_flg) return;
//     if(c<2 && n==N) return;
//     if(c==2){
//         if(n==N){
//             cout<<"POSSIBLE"<<endl;
//             e_flg=true;
//         }
//         return;
//     }
//     for(int i = 1; i <= N; i++){
//         if(i==n) continue;
//         vector<int>::iterator ni = find(ED[n].begin(),ED[n].end(),i);
//         if(ni!=ED[n].end()) dfs(i,c+1);
//     }
// }

int main(void){
    cin.sync_with_stdio(false);
    cin>>N>>M;
    vector<int> ap;
    set<int> bp;
    // for(int i = 0; i <= N; i++){
    //     vector<int> v;
    //     ED.push_back(v);
    // }
    for(int i = 0; i < M; i++){
        int a,b;
        cin>>a>>b;
        if(a==1){
            ap.push_back(b);
            continue;
        }
        if(b==N){
            bp.insert(a);
            continue;
        }
        
        // ED[a].push_back(b);
    }
    // dfs(1,0);
    // if(e_flg==false) cout<<"IMPOSSIBLE"<<endl;
    for(int i = 0; i < ap.size(); i++){
        if(bp.find(ap[i]) != bp.end()){
            cout<<"POSSIBLE"<<endl;
            return 0;
        }
    }
    cout<<"IMPOSSIBLE"<<endl;
    return 0;
}

Measured memory_bytes: 5368
#include "bits/stdc++.h"
using namespace std;
#define int long long
#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 FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;}
template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;}
constexpr int INF = 1e9;



signed main(){
	string s;
	cin >> s;
	vector<int>cnt(2020);
	int sum = 0,ans = 0;
	REP(i,s.size()){
		vector<int>ncnt(2020);
		ncnt[s[i] - '0']++;
		REP(j,2020){
			if(cnt[j] == 0)continue;
			int nex = j * 10 + (s[i] - '0');
			nex %= 2019;
			ncnt[nex] += cnt[j];
		}
		ans += ncnt[0];
		cnt = ncnt;
	}
	out(ans);
}

Measured memory_bytes: 3752
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int cl(int a, int b) {
	return (a - (a%b)) / b;//b=0だと積む
}
int up(int a, int b) {
	return cl(a + b - 1, b);//b=0だと積む
}
int ord(int a, int p) {
	if (a%p == 0) {
		return ord(a / p, p) + 1;
	}
	else {
		return 0;
	}
}
long long ruin(int a, int n, long long  p) {
	if (n == 0) {
		return (1%p);
	}
	else {
	long long x = ruin(a, (n - (n % 2)) / 2, p);
		if (n % 2 == 0) {
			return (x*x) % p;
		}
		else {
			return (((x*x) % p)*a) % p;
			
		}
	
	}
	
}
long long com(int n, int r, int p) {
	if (r == 0) {
		return (1%p);
	}
	else {
		long long x = com(n, r - 1, p);
		return (x*(n - r) / r) % p;
	}
}
int main()
{
	int n, q; long long t;
	cin >> n >> t >> q;
	vector<long long> a(n);
	vector<int> d(n);
	vector<int> e(q);
	vector<long long>ans(q);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> d[i];
	}
	for (int i = 0; i < q; i++) {
		int x;
		cin >> x;
		e[i] = x - 1;
	}
	int ba = 2;
	vector<int> nu(n);
	vector<int> ch(n);
	int si = 0;
	int no = -1;//kesu
	for (int i = 0; i < n; i++)
	{
		if (d[i] != ba) {
			ch[si] = i;
			si++;
			no++;
			ba = d[i];
		}
		nu[i] = no;
	}
	for (int i = 0; i < q; i++) {
		int p = e[i];
		int x = nu[p];
		int y = x + (1 - ((x+2) % 2));
		if (y < 0) {
			cout << a[p] - t << endl;
		}
		else if (y >= si) {
			cout << a[p] + t << endl;
		}
		else {
			long long me = (a[ch[y]] + a[ch[y] - 1]) / 2;
			if (d[p] == 1) {
				cout << min(a[p] + t, me) << endl;
			}
			else {
				cout << max(a[p] - t, me) << endl;
			}
		}
	}
}



Measured memory_bytes: 4600
S = int(input())
mod = 10**9+7

if S <= 2:
    print(0)
elif S == 3:
    print(1)
else:
    maxlen = S//3
    ans = 0
    
    facs = [1] * 2000
    invs = [1] * 2000
    nfac = 1
    for i in range(1, 2000):
        nfac = nfac * i % mod
        facs[i] = nfac
        invs[i] = pow(facs[i], mod-2, mod)
    
    for l in range(1, maxlen+1):
        r = S-(3*l)
        # 残りをどう振り分けるか
        # 重複組合せ, rem個ある1に仕切りをl-1個入れる
        combs = facs[l-1+r] * invs[r] * invs[l-1] % mod
        ans += combs
        ans %= mod

    print(ans)


Measured memory_bytes: 65404
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  const ll MOD = 1e9+7;
  int N;cin >> N;
  ll ans = 1;
  repp(i,1,N+1){
    ans *= (ll)i;
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Your code here!
    
    int n;
    scanf("%d",&n);
    
    int i,p[4],r;
    
    for(i=0;i<3;++i){
        
        r = n%10;
        n = n/10;
        p[i] = r;
        
    }
    
    
    for(i=0; i<3;++i){
        
        if(p[i] == 1)  p[i] = 9;
        else if (p[i] == 9) p[i] = 1;
        
    }
    
    printf("%d%d%d",p[2],p[1],p[0]);
    
    
    return 0;
}


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

long long int w[100005];
long long int v[100005];
int n,t;
long long int dp[100005][100];

long long int solve(int x,int k){
    if(x == n || k<0 )
        return 0;
    if(dp[k][x] != -1)
        return dp[k][x];
    dp[k][x] = (k-w[x] >= 0) ? ( max(solve(x+1,k), v[x]+solve(x+1,k-w[x])) ) : ( solve(x+1,k) );
    return dp[k][x];
}

int main(){
    cin >> n >> t;
    for(int i=0;i<100005;i++){
        for(int j=0;j<n;j++)
            dp[i][j] = -1;
    }

    for(int i=0;i<n;i++){
        cin >> w[i] >> v[i];
    }
    cout << solve(0,t) << endl;
}


Measured memory_bytes: 78336
#pragma GCC optimize(2)
#pragma GCC optimize(3)   
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector < ll > vl;
typedef vector < vl > vvl;
typedef pair < ll, ll > pll;
typedef vector < pair < ll, ll > > vpll;
#define kill freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define pb push_back
#define fo(i,n) for(ll i=0;i<n;i++)
#define rev(i,n) for(ll i=n-1;i>=0;i--)
#define all(c) c.begin(), c.end()
#define go(c,it) for(auto it=(c).begin(); it!=(c).end(); it++)
#define fi first
#define se second
#define MOD 998244353
#define Boost() ios_base::sync_with_stdio(false);cin.tie(NULL)
#define MOD1 1000000007
ll power(ll a, ll b){ll res=1;a=a%MOD;while(b>0){if(b&1){res=(res*a)%MOD;}a=(a*a)%MOD;b>>=1;}return res;}
ll fermat_inv(ll y){return power(y,MOD-2);}
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
#define oo 100000000000000000
const ll dx[]={-1,0,1, 0,-1,1, 1,-1};
const ll dy[]={ 0,1,0,-1, 1,1,-1,-1};

void solve(){
    ll n,k;
    cin>>n>>k;
    ll a[n];
    fo(i,n)cin>>a[i];
    ll ans = 0;
    vl v;
    fo(i,k)ans+=a[i];
    v.pb(ans);
    for(ll i=k;i<n;i++){
        ans+=a[i];
        ans-=a[i-k];
        v.pb(ans);
    }
    fo(i,v.size()-1){
        if(v[i+1]>v[i])cout<<"Yes\n";
        else cout<<"No\n";
    }
}

int main(){
    Boost();
    ll T = 1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 6788
#include <iostream>
#include <bits/stdc++.h>
#define ll long long

using namespace std;
ll r1,c1,Fact[3000100],r2,c2;
const ll Mod = 1e9 + 7;

long long fastpower(long long a,long long b)
{
    if(b==0)
        return 1;
    if(b==1)
        return a;
    long long res = fastpower(a,b/2)%Mod;
    res = (res %Mod  * res % Mod )%Mod;
    if(b%2!=0)
        res*=a;
    return res % Mod;
}

ll mul_self(ll &x , ll y){
    x = (x * y)%Mod;
}

ll add_self(ll &x , ll y){
    x = (x + y)%Mod;
}


ll C(ll n , ll k){
    if(n - k < 0)   return 1;
    ll x = 1;
    mul_self(x , Fact[k]);
    mul_self(x , Fact[n - k]);
    ll y = Fact[n];
    mul_self(y , fastpower(x , Mod - 2));
    return y;
}

int main()
{
    cin >> r1 >> c1 >> r2 >> c2;
    Fact[0] = 1;
    for(int i = 1;i<=3e6;i++) Fact[i] = (Fact[i - 1] * i)%Mod;
    ll Ans = 0 , dif = r2 - r1;
    for(int i = c1;i<=c2;i++)  {
        ll Res = C(i + r1 + dif + 1, i + 1) - C(i + r1 , i + 1) + 2 * Mod;
        add_self(Ans , Res);
    }
    cout << Ans;
    return 0;
}


Measured memory_bytes: 23680
n,m=gets.split.map(&:to_i)
abs=[]

m.times do
  abs << gets.split.map(&:to_i)
end


abs = abs.sort_by {|a,b|
  [a,b]
}

if m == 1
  puts '1'
  exit 0
end

i = 0
j = 1
ret = []
a = abs[i]
b = abs[j]
while j < m
  # p '==========='
  #p [a,b]
  # bがaを含む
  if a[0] == b[0]
    j += 1
    b = abs[j]
  # aがbを含む
  elsif b[1] <= a[1]
    j += 1
    a = b
    b = abs[j]
  # かぶらない
  elsif a[1] <= b[0]
    ret << a
    i = j
    j = i+1
    a = abs[i]
    b = abs[j]
    break if b.nil?
  # 一部かぶる
  else
    j += 1
    a = [b[0],a[1]]
    b = abs[j]
  end
  #p ret
end

ret << a

p ret.count

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

const double pi = 3.14159265358979323846;
const ll mod = 1000000007;


int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	ll n; cin >> n; 
	vector<ll> a(n);
	rep(i,n) cin >> a.at(i);
	sort(a.rbegin(), a.rend());
	ll ans = a.at(0);
	int cnt = 2;
	for(int i = 1; i < n; i++){
		for(int j = 0; j <= 1; j++){
			if(cnt >= n) break;
			cnt++;
			ans += a.at(i);
		}
	}
	cout << ans << endl;
} 

Measured memory_bytes: 4772
import sys
N,K = map(int,input().split())
S = input()
l_edge = []
r_edge = []

if S[0] == '0':
    l_edge.append(0)
for i in range(N):
    # iは0ブロックの左端になっているか
    if i > 0 and (S[i-1] == '1' and S[i] == '0'):
        l_edge.append(i)
    # iは0ブロックの右端になっているか
    if i < N-1 and (S[i] == '0' and S[i+1] == '1'):
        r_edge.append(i)
if S[-1] == '0':
    r_edge.append(N-1)

assert len(l_edge) == len(r_edge)

Block = len(l_edge)
if Block <= K:
    print(N)
    sys.exit()

ans = 0
for leftblock in range(Block):
    # l := 「1の列の左端」のSにおけるインデックス
    if leftblock == 0:
        l = 0
    else:
        l = r_edge[leftblock-1]+1
        assert l>0

    rightblock = max(leftblock+K-1,0)
    if rightblock >= Block-1:
        r = N-1
    else:
        r = l_edge[rightblock+1]-1
    
    '''
    print('----')
    print(leftblock,rightblock)
    print(l,r)
    '''
    ans = max(ans,r-l+1)

print(ans)
    


    

Measured memory_bytes: 78648
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using P = pair<int, int>;

int main() {
  int key = 1;
  int a[7];
  rep(i, 7) {
    a[i] = key;
    key *= 10;
  }
  int N;
  cin >> N;
  string n = to_string(N);
  int cnt = n.size();
  if(cnt == 1) {
    cout << N << endl;
    return 0;
  }
  int ans = 0;
  for(int i = 1; i <= N; i++) {
    string s = to_string(i);
    char top = s[0];
    char bot = s[s.size()-1];
    int t = 2;
    if(bot == '0') continue;
    if(top == bot) {
      t = 1;
    }
    while(t <= cnt) {
      if(t == cnt) {
        if(bot == n[0]) {
          if(cnt >= 3) {
            rep(i, cnt-2) {
              ans += (n[i+1] - '0') * a[cnt-i-3];
            }
          }
          if(top <= n[n.size()-1]) {
            ans += 1;
          }
        } else if(bot < n[0]) {
          ans += a[t-2];
        }

      } else {
        if(t == 1) {
          ans += 1;
        } else {
          ans += a[t-2];
        }
      }
      t++;
    }
    // cout << i << " " << ans << endl;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3648
/*
god taekyu
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n,q;
int A[100005];
int vt[100005];
void pro(int x) {
    for(int i=1;i<=n;i++) vt[i] = 0;
    for(int i=1;i<=n/2;i++) {
        for(int j=n;j>=1;j--) {
            if(vt[j] == 0) {
                vt[j] = 1;
                cout<<A[j]<<' ';
                break;
            }
        }
        int jidx = -1;
        for(int j=1;j<=n;j++) {
            if(vt[j] == 0) {
                if(jidx == -1) jidx = j;
                else {
                    if(abs(x - A[jidx]) > abs(x - A[j])) jidx = j;
                }
            }
        }
        vt[jidx] = 1;
    }
    for(int i=1;i<=n;i++) if(vt[i] == 0) cout<<A[i];
    cout<<'\n';
}
int dp[100005];
ll X[100005];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>A[i];
    sort(A+1,A+n+1);

    for(int i=0;i<=20;i++) {
        //cout<<i<<" : ";
        //pro(i);
    }

    int r = n/2 + 1;
    int l = 2;
    if(n%2) l--;
    int cnt=0;
    ll sum = 0;
    for(int i=r;i<=n;i++) sum += (ll)A[i];
    while(l<r) {
        //cout<<(A[l]+A[r])/2<<'\n';
        dp[cnt++] = (A[l]+A[r])/2;
        X[cnt-1] = sum;

        sum -= (ll)A[r];
        sum += (ll)A[l];
        l+=2;
        r++;
    }
    X[cnt] = sum;
    while(q--) {
        int a; cin>>a;
        int idx = lower_bound(dp,dp+cnt,a) - dp;
        cout<<X[idx]<<'\n';
    }
    for(int i=0;i<cnt;i++) {
        //cout<<dp[i]<<' ';
    }
    //cout<<'\n';
    return 0;
}

/*
god taekyu
*/


Measured memory_bytes: 2688
#include <iostream>

using namespace std;

#define MAX_H 55
#define MAX_W 55

int W, H;

int C[MAX_H][MAX_W];

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

void dfs(int x, int y)
{
	if (C[y][x] == 1)
	{
		C[y][x] = 0;

		for (int i = 0; i < 8; i++)
		{
			if (0 <= x + dx[i] && x + dx[i] <= W - 1 && 0 <= y + dy[i] && y + dy[i] <= H - 1)
			{
				if (C[y + dy[i]][x + dx[i]] == 1)
				{
					dfs(x + dx[i], y + dy[i]);
				}
			}
		}
	}
}

int main()
{
	while (true)
	{
		cin >> W >> H;

		if (W == 0 && H == 0) { break; }

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				cin >> C[i][j];
			}
		}

		int count = 0;

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				if (C[i][j] == 1)
				{
					dfs(j, i);

					count++;
				}
			}
		}

		cout << count << endl;
	}

	return 0;
}

Measured memory_bytes: 1240
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define all(v) (v).begin(), (v).end()

struct restaurant
{
    int index, rating;
    string name;

    restaurant(int i, int r, string S)
    {
        index = i, rating = r, name = S;
    }

    const int operator <(const restaurant &R)
    {
        if(name == R.name)
        {
            return (rating > R.rating);
        }
        else
        {
            return (name < R.name);
        }
    }
};

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

    vector <restaurant> R;
    for(int i = 1; i <= no_of_restaurants; i++)
    {
        string name;
        int rating;

        cin >> name >> rating;

        R.push_back(restaurant(i, rating, name));
    }

    sort(all(R));

    for(int i = 0; i < no_of_restaurants; i++)
        cout << R[i].index << endl;

    return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
ll mo;
vector<int> E[101010];
vector<ll> dp[101010];

ll dfs(int cur,int pre) {
	ll ret=1;
	int i;	
	FOR(i,E[cur].size()) {
		int e=E[cur][i];
		if(e!=pre) {
			dp[cur][i]=dfs(e,cur);
			(ret*=(1+dp[cur][i]))%=mo;
		}
	}
	return ret;
}

void dfs2(int cur,int pre,ll p) {
	int i;
	FOR(i,E[cur].size()) {
		int e=E[cur][i];
		if(e==pre) dp[cur][i]=p;
	}
	vector<ll> L(E[cur].size()),R(E[cur].size());
	FOR(i,E[cur].size()) {
		L[i]=(i?L[i-1]:1)*(1+dp[cur][i])%mo;
	}
	for(i=E[cur].size()-1;i>=0;i--) {
		R[i]=((i<E[cur].size()-1)?(R[i+1]):1)*(1+dp[cur][i])%mo;
		if(E[cur][i]!=pre) {
			ll tot=(i?L[i-1]:1)*((i<E[cur].size()-1)?R[i+1]:1)%mo;
			dfs2(E[cur][i],cur,tot);
		}
		
	}
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) dp[i].resize(E[i].size());
	ll tot=dfs(0,-1);
	dfs2(0,-1,0);
	
	FOR(i,N) {
		ll tot=1;
		FORR(d,dp[i]) (tot*=(1+d))%=mo;
		cout<<tot<<endl;
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 23424
#include <bits/stdc++.h> 
using namespace std;
///////////////////////////////////////////
const long long int INF = INT32_MAX;
const long long int Mod = 1000000007;
const long long int mod = 100000;//10^5
using ll = long long int; //long long int は64bit
using ci = const int; using vi = vector<int>; using Vi = vector<long long int>; using pii = pair<int,int>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
#define np nullptr
template<class T>bool chmax(T &former, const T &b) { if (former<=b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define fill(x,num) memset(x,num,sizeof(x));
typedef vector<vector<ll> > matrix;
//       cin.tie(0);ios::sync_with_stdio(false);
void cinit(){cin.tie(0);ios::sync_with_stdio(false);}
//////////////////////////^^ *Emile ^^^//////////////////////////////////////////////////////

int main(){
	string s;ll ans = 0;ll num = 0;
	cin>>s;
	bool key = true;
	rep(i,s.size()){
		if(s[i]=='W'){
			num++;
			ans += i-num+1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifdef LOCAL
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif

#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)

typedef long long ll;

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

    int N, L;
    cin >> N >> L;
    vector<int> taste(N);

    REP(i, N) { taste[i] = L + i; }
    debug(taste);
    ll sum = 0;
    if (L >= 0) {
        taste.erase(taste.begin());
    } else {  // Lは負
        int pos = min(N - 1, -L);
        debug(pos);
        taste.erase(taste.begin() + pos);
    }

    REP(i, N - 1) { sum += taste[i]; }
    debug(taste);
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vl=vector<ll>;
#define MOD 1000000007
ll mod_pow(ll x, ll p){
	ll res=1;
	ll n=x;
	while(p>0){
		if(p&1==1)res=(res*n)%13;
		n=(n*n)%13;
		p=(p>>1);
	}
	return res;
}
int ctoi(char c){
    return (int)c-(int)'0';
}
int main() {
    string S; cin>>S;
    int N=S.size();
    vector<vl> dp(N+1,vl(13,0));
    if(S[0]=='?'){
        for (int i = 0; i < 10; i++){
            int rem=(i*mod_pow(10,N-1))%13;
            dp[0][rem]++;
        }
    }else{
        dp[0][ctoi(S[0])]=1;
    }
    for (int i = 1; i <= N; i++){
        if(S[i-1]=='?'){
            for (int j = 0; j < 10; j++){
                int rem=(j*mod_pow(10,N-i))%13;
                if(i==1){
                    dp[1][rem]++;
                }else{
                    for (int k = 0; k < 13; k++){
                        dp[i][(k+rem)%13]+=dp[i-1][k];
                        dp[i][(k+rem)%13]%=MOD;
                    }
                }
            }
        }else{
            int rem=(ctoi(S[i-1])*mod_pow(10,N-i))%13;
            if(i==1){
                dp[1][rem]=1;
            }else{
                for (int k = 0; k < 13; k++){
                    dp[i][(k+rem)%13]+=dp[i-1][k];
                    dp[i][(k+rem)%13]%=MOD;
                }
            }
        }
    }
    cout<<dp[N][5]<<endl;
}

Measured memory_bytes: 16616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
mt19937 rnd;



int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    ll n, m;
    cin >> n >> m;
    if (n == 1 || m == 1) {
        cout << "1\n";
    }
    else {
        cout << (n * m + 1) / 2 << "\n";
    }

#ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


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

import math

def main(N,C,S,F):
    ans = [0]*N
    for i in range(N-2):
        tmp = S[i]+C[i]
        for j in range(i+1,N-1):
            if tmp<S[j]:
                tmp = S[j]
            elif tmp>S[j] and (tmp-S[j])%F[j]!=0:
                part = math.ceil((tmp-S[j])/F[j])
                tmp = S[j]+F[j]*part
            tmp += C[j]
        ans[i] = tmp
    ans[-2] = C[-1]+S[-1]
    
    for i in ans:
        print(i)

if __name__ == '__main__':
    N = int(input())
    C,S,F = [],[],[]
    for i in range(N-1):
        c,s,f = map(int, input().split())
        C.append(c)
        S.append(s)
        F.append(f)
    main(N,C,S,F)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod107 1000000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(), v.end()
#define PI acos(-1)

const ll INF = 10010001010;
const int inf = 1000034000;
typedef vector<ll> vecl;
typedef vector<int> veci;
typedef tuple<string, int, int> TUP;

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

vector<pair<long long, long long>> prime_factorize(long long N)
{
    vector<pair<long long, long long>> res;
    for (long long a = 2; a * a <= N; ++a)
    {
        if (N % a != 0)
            continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0)
        {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1)
        res.push_back({N, 1});
    return res;
}

uintmax_t combination(unsigned int n, unsigned int r)
{
    if (r * 2 > n)
        r = n - r;
    uintmax_t dividend = 1;
    uintmax_t divisor = 1;
    for (unsigned int i = 1; i <= r; ++i)
    {
        dividend *= (n - i + 1);
        divisor *= i;
        
    }
    return dividend / divisor;
}

int main()
{
    ll N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N;i++)
    {
        cin >> A[i];
    }
    sort(all(A));
    reverse(all(A));
    ll width = 0;
    ll height = 0;
    for (int i = 0; i < N; i++)
    {
        if(A[i] == A[i+1] && width == 0){
            width = A[i];
            i++;
            continue;
        }
        if (A[i] == A[i + 1] &&height == 0)
        {
            height = A[i];
            break;
        }
    }
    cout << width * height << endl;
}


Measured memory_bytes: 3792
#include <bits/stdc++.h>
#define FOR(i,s,e) for(int i=(s);i<(e);i++)
#define REP(i,n) FOR(i,0,n)
#define all(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;
typedef pair<int, int> P;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N){
       cin >> A[i];
       A[i] -= i;
    }
    sort(all(A));
    LL ans = 0;
    REP(i, N) ans += abs(A[i] - A[N/2]);
    cout << ans << endl;
    
    
    return 0;
}


Measured memory_bytes: 1024
n = int(input())
a = []
for i in range(n):
    a.append(int(input())-1)
button = 0 
push = 0
while a[button] != -1:
    push += 1
    tmp = a[button]
    a[button] = -1
    button = tmp 
    if button == 1:
        print(push)
        exit()
print(-1)

Measured memory_bytes: 7084
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll gcd(ll x, ll y) {
    if(y == 0) {
        return x;
    }
    return gcd(y, x%y);
}

ll GCD(vl &v) {  // vの全要素のgcd
    ll res = v[0];
    rep(i, v.size()) {
        res = gcd(res, v[i]);
    }
    return res;
}

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

    vl x(n+1);
    cin >> x[0];
    exrep(i, 1, n) {
        cin >> x[i];
    }
    sort(all(x));

    vl L(n);
    rep(i, n) {
        L[i] = x[i+1] - x[i];
    }
    
    out(GCD(L));
    re0;
}

Measured memory_bytes: 1792