akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;

int n, sign;
ll a[N], k, x, y, z, neg, pos, zero;

int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    if (a[i] < 0) ++x;
    else if (a[i] > 0) ++y;
    else ++z;
  }
  sort(a + 1, a + 1 + n);
  neg = x * y;
  pos = y * (y - 1) / 2 + x * (x - 1) / 2;
  zero = 1LL * n * (n - 1) / 2 - neg - pos;
  if (k > neg + zero) sign = 1; // positive
  else if (k > neg) sign = 0; // zero
  else sign = -1; // negative

  if (sign == 0) {
    cout << 0;
    return 0;
  } else if (sign == 1) {
    ll lt = 1, rt = 1e18, ans = -1;
    k -= neg + zero;
    while (lt <= rt) {
      ll mid = (lt + rt) >> 1;
      ll cnt = 0;
      int j = x + z;
      for (int i = n; i >= 1; --i) {
        if (a[i] <= 0) break;
        j = min(j, i - 1);
        while (j + 1 <= i - 1 && a[j + 1] * a[i] <= mid) ++j;
        cnt += (ll)(j - x - z);
      }
      j = x + 1;
      for (int i = 1; i <= n; ++i) {
        if (a[i] >= 0) break;
        j = max(j, i + 1);
        while (j - 1 >= i + 1 && a[j - 1] * a[i] <= mid) --j;
        cnt += (ll)(x + 1 - j);
      }
      if (cnt >= k) {
        ans = mid;
        rt = mid - 1;
      } else {
        lt = mid + 1;
      }
    }
    cout << ans;
  } else {
    ll lt = -1e18, rt = -1, ans = -1;
    while (lt <= rt) {
      ll mid = (lt + rt) >> 1;
      ll cnt = 0;
      int j = 0;
      for (int i = 1; i <= n; ++i) {
        if (a[i] <= 0) continue;
        while (j + 1 <= n && a[j + 1] * a[i] <= mid) ++j;
        cnt += (ll)j;
      }
      if (cnt >= k) {
        ans = mid;
        rt = mid - 1;
      } else {
        lt = mid + 1;
      }
    }
    cout << ans;
  }
  return 0;
}

Measured memory_bytes: 1792
package main

import "fmt"

const inf int = 1e12

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	var a, b, c int
	as := make([]int, m)
	cs := make([]int, m)
	for i := 0; i < m; i++ {
		fmt.Scan(&a, &b)
		as[i] = a
		for j := 0; j < b; j++ {
			fmt.Scan(&c)
			cs[i] |= 1 << (c - 1)
		}
	}

	dp := make([][]int, m+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, 1<<n)
		for j := 0; j < len(dp[i]); j++ {
			dp[i][j] = inf
		}
	}
	dp[0][0] = 0

	for i := 0; i < m; i++ {
		for j := 0; j < 1<<n; j++ {
			dp[i+1][j] = min(
				dp[i+1][j],
				dp[i][j],
			)

			dp[i+1][j|cs[i]] = min(
				dp[i+1][j|cs[i]],
				dp[i][j]+as[i],
			)
		}
	}

	ans := dp[m][(1<<n)-1]
	if ans == inf {
		ans = -1
	}

	fmt.Println(ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}


Measured memory_bytes: 35384
/**
*	created: 09.09.2020 23:44:10
**/
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
using ll = long long;
using P = pair<int,int>;
// #define endl '\n'
#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 rep2(i,s,n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
const long double pi = acos(-1.0);
const int MAX = 1000010;
const int INF = 1ll << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;
template<typename T> inline bool chmax(T &a, T &b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T> inline bool chmin(T &a, T &b) {if (b < a) {a = b; return 1;} return 0;}
template<typename T> T pow(T a, ll n) {T r(1); while(n) {if (n & 1) r *= a; a *= a; n >>= 1;} return r;}
struct faster_io {faster_io() {cin.tie(0); ios_base::sync_with_stdio(false);}} faster_io_;

vector<int> g[MAX];
vector<P> bri;
vector<int> art;
int ord[MAX], low[MAX];
bool vis[MAX];

void lowlink(int v, int p, int &k) {
    vis[v] = true;
    ord[v] = k++;
    low[v] = ord[v]; // initialize lowlink
    bool isart = false;
    int cnt = 0;
    for (auto i : g[v]) {
        if(!vis[i]) {
            cnt++;
            lowlink(i,v,k);
            chmin(low[v],low[i]);
            if (!p && ord[v] <= low[i]) isart = true;
            if (ord[v] < low[i]) bri.push_back(P(min(v,i),max(v,i)));
        }
        else if (i != p) chmin(low[v],ord[i]);
    }
    if (p == -1 && cnt > 1) isart = true;
    if(isart) art.push_back(v);
}

signed main() {
    int n, m; cin >> n >> m;
    rep(i,m) {
        int a, b; cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int k = 0;
    rep(i,n) if(!vis[i]) lowlink(i,-1,k);
    cout << bri.size() << endl;
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> s(n);
  for (int i=0;i<n;++i) {
    cin >> s[i];
  }
  int count=0;
  for (int i=0;i<(n-2);++i) {
    if (s[i]<s[i+1] & s[i+1]<s[i+2]) {
      count+=1;
    } else if (s[i+2]<s[i+1] & s[i+1]<s[i]) {
      count+=1;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
//#include<cmath>
//#include<algorithm>
#include<cstring>
//#include<map>
using namespace std;
inline int read()
{
    int p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;}
char a[101];
int main()
{
	int A=read(),B=read();
	cin>>a;
	if(strlen(a)!=A+B+1){cout<<"No";return 0;}
	if(a[A]!='-'){cout<<"No";return 0;}
	for(int i=0;i<strlen(a);i++)
	    if(i!=A)
		   if(a[i]<'0'||a[i]>'9')
		      {cout<<"No";return 0;}
	cout<<"Yes";
    return 0;
}

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

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

using namespace std;

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

    ll a;
    string s;
    cin >> a >> s;
    if (a >= 3200) cout << s << endl;
    else cout << "red" << endl;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<string> vs;
const ll mod = 1e9+7;
const ll inf = 1e17;
const int INF = 1e9;
const double PI = acos(-1);
#define fo(i, a, b) for (int i = a; i < b; i++)
#define re(i, n) fo(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(s) s.begin(), s.end()
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
int main()
{
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;

  int x3, y3, x4, y4;
  x3 = x2 - (y2 - y1); cout << x3 << ' ';
  y3 = y2 + (x2 - x1); cout << y3 << ' ';
  x4 = x3 - (y3 - y2); cout << x4 << ' ';
  y4 = y3 + (x3 - x2); cout << y4 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

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

    if(30<=n)yn;
    return 0;
}




Measured memory_bytes: 3616
# 要復習
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    A = LIST()
    B = LIST()
    C = LIST()

    benefit = 0
    for i in range(N - 1):
        if A[i+1]-A[i] == 1:
            benefit += C[A[i]-1]
            # print(benefit)

    for i in range(N):
        benefit += B[A[i]-1]
    print(benefit)
if __name__ == "__main__":
    main()




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

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

    vector<int> data(n);
    for (int i = 0; i < n; i++){
        cin >> data.at(i);
    }
    bool ret = false;
    int max = 0;
    for (int i = 0; i < n; i++){
        
            if (max - 1 > data.at(i)){
                ret = true;
            }
        
        if (max < data.at(i)){
            max = data.at(i);
        }
    }

    cout << (ret ? "No" : "Yes") << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,s,e) for(int i=(s); i<(e); i++)
#define pb(n) push_back((n))
#define mp(n,m) make_pair((n),(m))
#define all(r) r.begin(),r.end()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;




int main() {
	int n;
	while (cin >> n&&n > 0) {
		vi v(n);
		rep(i, n)cin >> v[i];
		sort(all(v));
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			ans += v[i] * (v.size() - (i + 1));
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1248
#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;

signed main(){
  int n,m;
  cin>>n>>m;
  vector<vector<int> > d(m,vector<int>(m));
  for(int i=0;i<m;i++){
    for(int j=0;j<m;j++)cin>>d[i][j];
  }
  vector<vector<int> > c(n,vector<int>(n));
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++)cin>>c[i][j];
  }
  vector<int> a0(m+1,0);
  vector<int> a1(m+1,0);
  vector<int> a2(m+1,0);

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if((i+j+2)%3==0)a0[c[i][j]-1]++;
      if((i+j+2)%3==1)a1[c[i][j]-1]++;
      if((i+j+2)%3==2)a2[c[i][j]-1]++;
    }
  }
  int ans=1e9;
  int tmp=0;
  for(int i=0;i<m;i++){
    for(int j=0;j<m;j++){
      for(int k=0;k<m;k++){
        if(i==j||j==k||k==i)continue;
        for(int z=0;z<m;z++)tmp+=d[z][i]*a0[z];
        for(int z=0;z<m;z++)tmp+=d[z][j]*a1[z];
        for(int z=0;z<m;z++)tmp+=d[z][k]*a2[z];
        ans=min(ans,tmp);
        tmp=0;
      }
    }
  }
  cout<<ans<<endl;
}


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

int main() {

    int N;
    cin >> N;

    map<string, int> S;
    for (int i = 0; i < N; i++)
    {
        string s; cin >> s;
        S[s]++;
    }

    int maxv = 0;
    for (auto x:S) {
        maxv = max(x.second, maxv);
    }

    for (auto x:S) {
        if (x.second == maxv) {
            cout << x.first << endl;
        }
    }
}

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

#define REP(i,n) for(int i=0; i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
using namespace std;

int main() {
	int n;
	cin >> n;
	VI v(n);
	int res = 0;
	REP(i, n) {
		cin >> v[i];
	}
	sort(ALL(v));
	reverse(ALL(v));
	REP(i, n) {
		if (i % 2 == 0) {
			res += v[i];
		}
		else {
			res -= v[i];
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
int main(void)
{
    int A,B,N;
    scanf("%d%d%d",&N,&A,&B);
    if(N==1)
    {
        if(A==B)
            printf("1\n");
        else
            printf("0\n");
    }
    else 
    {
        if(A>B)
            printf("0\n");
        else
            printf("%lld\n",(long long )(B-A)*(N-2)+1);
    }
    return 0;
}

Measured memory_bytes: 760
x, n = map(int, input().split())
if(n > 0):
  p = list(map(int, input().split()))
  lists = list(range(102))
  del lists[0]
  sa = []
  for i in lists:
    if(i in p):
      sa.append(999)
    else:
      sa.append(abs(x-i))
    ind = sa.index(min(sa))
    ans = lists[ind]
else :
  ans = x
if (x <= ans - x):
  ans = 0
print(ans)

Measured memory_bytes: 9152
#include<stdio.h>
int main(){
  int x,y;
  scanf("%d%d",&x,&y);
  
  for (int c=0;c <= x;c++){
    int t =x-c;
    int asi = c*2+t*4;
    if(asi==y){
      printf("Yes");
      return 0;
    }
  }
    printf("No");
    return 0;
  }
  


Measured memory_bytes: 1732
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
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; }

using ll = long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class DRGBTriplets {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int n; cin >> n;
      string s; cin >> s;
      ll red = 0, green = 0, blue = 0;
      rep(i, n) {
        if (s[i] == 'R') {
          red++;
        } else if (s[i] == 'G') {
          green++;
        } else {
          blue++;
        }
      }
      ll all = red*green*blue;
      for(int i=1; i<n; i++) {
        for(int j=0; j<n; j++) {
          if (j+i+i>=n) continue;
          if (s[j] != s[j+i] && s[j+i] != s[j+i+i] && s[j+i+i] != s[j]) {
            all--;
          }
        }
      }
      cout << all << endl;

    }
};

signed main() {
  DRGBTriplets solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<algorithm>
#include<string>
#include<cassert>
#include<vector>
using namespace std;

#define sz(x) (int)(x.size())
#define fr(i,a,b) for(int i=a;i<b;++i)
#define fdr(i,a,b) for(int i=b-1;i>=a;--i)
#define pb push_back
////////////////

int const N = 5e6 + 41;

string s;
vector<int> a, vans;

int d[N][2];

vector<int> vec(int n){
	vector<int> ret;
	if(n == 0) ret.pb(0);
	while(n){
		ret.pb(n % 10);
		n /= 10;
	}
	return ret;
}

int getSum(int p, int f){
	if(p >= sz(vans)){
		if(d[p][f] != -1){
			return d[p][f];
		}else{
			if(p >= sz(a)) return f;
			d[p][f] = (a[p] + f) % 10;
			int nf = (a[p] + f) / 10;
			d[p][f] += getSum(p+1, nf);
			return d[p][f];
		}
	}else{
		int ret = (a[p] + f + vans[p]) % 10;
		int nf = (a[p] + f + vans[p]) / 10;
		ret += getSum(p+1, nf);
		return ret;
	}
}

void solve(){
	cin >> s;
	fr(i, 0, N) fr(j, 0, 2) d[i][j] = -1;
	fr(i, 0, sz(s)) a.pb(s[sz(s)-1-i] - '0');
	int add = 0;
	fr(i, 0, sz(a)){
		a[i] *= 9;
		a[i] += add;
		add = a[i] / 10;
		a[i] %= 10;
	}
	if(add != 0) a.pb(add);
	fr(ans, 0, N){
		vans = vec(ans * 9);
		int sum = getSum(0, 0);
		if(sum <= ans * 9){
			cout << ans << endl;
			exit(0);
		}
	}
	assert(false);
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	solve();

	return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> lv(n);
    rep(i, n) cin >> lv[i];
    sort(lv.begin(), lv.end());
    int ans = 0;
    rep(b, n) rep(a, b) {
        int ab = lv[a] + lv[b];
        int r = lower_bound(lv.begin(), lv.end(), ab) - lv.begin();
        int l = b + 1;
        ans += max(0, r-l);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    S = input()
    hoge = defaultdict(int)
    for s in S:
        hoge[s] += 1
    keys = hoge.keys()
    if len(keys) == 2:
        a = list(set(hoge.values()))
        if len(a) == 1 and a[0] == 2:
            return True
    return False

if __name__ == '__main__':
    if main():
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 5588
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.D_Challenge
{
    class ABC_080
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            int[] nc = ReadInts();
            var stc = new int[nc[0]][];
            for (int i = 0; i < nc[0]; i++)
            {
                stc[i] = ReadInts();
            }
            /*Array.Sort(stc, (a, b) => a[2] - b[2]);
            var stcTemp = new List<int[]>();
            stcTemp.Add(stc[0]);
            int now = 0;
            for(int i = 1; i < stc.Length; i++)
            {
                if (stcTemp[now][2] == stc[i][2]
                    && stcTemp[now][1] == stc[i][0])
                {
                    stcTemp[now][1] = stc[i][1];
                }
                else
                {
                    stcTemp.Add(stc[i]);
                    now++;
                }
            }

            stc = stcTemp.ToArray();
            */
            Array.Sort(stc, (a, b) => a[0] - b[0]);
            var vList = new List<int[]>();
            for(int i = 0; i < stc.Length; i++)
            {
                /*
                Console.WriteLine(
                    stc[i][0] + " " + stc[i][1] + " " + stc[i][2]);*/
                bool canRec = false;
                for(int j = 0; j < vList.Count; j++)
                {
                    if ((vList[j][1]==stc[i][2] && vList[j][0]==stc[i][0])
                        ||vList[j][0] < stc[i][0])
                    {
                        vList[j][0] = stc[i][1];
                        vList[j][1] = stc[i][2];
                        canRec = true;
                        break;
                    }
                }
                if (!canRec)
                {
                    vList.Add(new int[2] { stc[i][1], stc[i][2] });
                }
            }
            Console.WriteLine(vList.Count);
        }

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


Measured memory_bytes: 24640
import sys
#input = sys.stdin.readline
input = sys.stdin.buffer.readline

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np


def main():
	xy=list(map(int,input().split()))
	ans=0
	li=[0,3,2,1]

	for i in xy:
		if i<=3:
			ans+=li[i]

	if sum(xy)==2:
		ans+=4

	print(ans*100000)







if __name__ == "__main__":
	main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;
 
int main() {
    int n, m, c; cin >> n >> m >> c;
    vector<int> b(m);
    rep(i, m) cin >> b[i];
    vector<vector<int> > a(n, vector<int>(m));
    rep(i, n)rep(j, m) cin >> a[i][j];

    int ans = 0;
    rep(i, n) {
        int judge = c;
        rep(j, m) judge += a[i][j]*b[j];
        if (judge > 0) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

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

int n;
int l[100010], r[100010];
set<P> stl, str;
int ans1, ans2;

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> l[i] >> r[i];
		stl.insert(make_pair(l[i], i));
		str.insert(make_pair(r[i], i));
	}
	int k = 0;
	while (!stl.empty()) {
		P x = *stl.rbegin();
		if (x.first <= k)break;
		ans1 += x.first - k;
		k = x.first;
		int p = x.second;
		stl.erase(x);
		str.erase(make_pair(r[p], p));
		if (str.empty())break;
		P y = *str.begin();
		if (k <= y.first)break;
		ans1 += k - y.first;
		k = y.first;
		p = y.second;
		str.erase(y);
		stl.erase(make_pair(l[p], p));
	}
	ans1 += abs(k);
	k = 0;
	stl.clear(); str.clear();
	for (int i = 0; i < n; i++) {
		stl.insert(make_pair(l[i], i));
		str.insert(make_pair(r[i], i));
	}
	while (!stl.empty()) {
		P y = *str.begin();
		if (k <= y.first)break;
		ans2 += k - y.first;
		k = y.first;
		int p = y.second;
		str.erase(y);
		stl.erase(make_pair(l[p], p));
		if (str.empty())break;
		P x = *stl.rbegin();
		if (x.first <= k)break;
		ans2 += x.first - k;
		k = x.first;
		p = x.second;
		stl.erase(x);
		str.erase(make_pair(r[p], p));
	}
	ans2 += abs(k);
	cout << max(ans1, ans2) << endl;
}

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

vector<int> dp(100001,-1);
map<int, vector<int>> mp;

int dfs(int in){
  if (dp[in] > 0) return dp[in];
  if (mp[in].empty()) return dp[in] = 0;
  else {
    for (auto k: mp[in]) dp[in] = max(dp[in], dfs(k)+1);
    return dp[in];
  }
}

int main(){
  int N, M;
  cin >> N >> M;
  for (int i=0; i<M; i++){
    int x, y; cin >> x >> y;
    mp[x].push_back(y);
  }
  for (int i=1; i<=N; i++) dfs(i);
  int ans = 0;
  for (int i=1; i<=N; i++) ans = max(ans, dp[i]);
  cout << ans << endl;
}


Measured memory_bytes: 14976
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		//入力データを変数で受け取る
		String s = sc.next();
		//入力データを処理して、結果を出力
		s = s.replace(",", " ");
		
		System.out.println(s);

	}
}




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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;





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

	string s; cin>>s;

	for(int i=0; i<s.size(); i++){
		if((i+1) %2 ==0){
			if(s[i] != 'L' && s[i] != 'U' && s[i] != 'D' ){
				writeln("No");
				return 0;
			}
		}else {
			if(s[i] != 'R' && s[i] != 'U' && s[i] != 'D'){
				writeln("No");
				return 0;
			}
		}
	}

	writeln("Yes");
}




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

import sys

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

N, x, y = MAP()
x -= 1; y -= 1
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

def dfs(x):
    dist  = [INF] * N
    stack = [(x, 0, -1)]
    while stack:
        u, cost, prev = stack.pop()
        if dist[u] != INF:
            continue
        dist[u] = cost
        for v in nodes[u]:
            if v == prev:
                continue
            stack.append((v, cost+1, u))
    return dist

res1 = dfs(x)
res2 = dfs(y)

mx = -INF
for i in range(N):
    if res1[i] <= res2[i]:
        mx = max(mx, res2[i])
print(mx - 1)


Measured memory_bytes: 74680
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> v;
ll n;
string s;
ll ff(string s){
    ll LL=0;
    for(int i=0;i<s.size();i++){
        LL+=ll(s[i]-'0');
        if(i!=s.size()-1)LL*=10;
    }
    return LL;
}
void f(string s){
    ll L=ff(s);
    if(L<=3234566667)v.push_back(L);
    else return ;
    if(s[s.size()-1]=='0'){f(s+'1');f(s+'0');}
    else if(s[s.size()-1]=='9'){f(s+'8');f(s+'9');}
    else{
        int c=s[s.size()-1]-'0';
        f(s+char(c+1+'0'));
        f(s+char(c-1+'0'));
        f(s+char(c+'0'));
    }
    return ;
}
int main(void){
    cin>>n;
    for(char i='1';i<='9';i++){
        string t="";
        t+=i;
        f(t);
    }
    sort(v.begin(),v.end());
    cout<<v[n-1]<<endl;
}


Measured memory_bytes: 1528
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var count = 0;
            for (int i = 0; i < S.Length / 2; i++)
            {
                if (S[i] != S[S.Length - i - 1])
                    count++;
            }

            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>

using namespace __gnu_pbds;
using namespace std;

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

template <typename T> using Set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V> using Umap = gp_hash_table<K, V>;

signed main(void){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, c;
    cin >> n >> c;

    vector<vector<int> > querys;
    vector<int> point(n + 1);

    vector<pair<int, int> > vec;

    for(int i = 1; i <= n; ++i){
        vec.emplace_back(make_pair(point[i], i));
    }

    for(int i = 0; i < c; ++i){
        int com;
        cin >> com;
        if(com == 0){
            int t, p;
            cin >> t >> p;
            querys.emplace_back(vector<int>{com, t, p});
            point[t] += p;
            vec.emplace_back(make_pair(point[t], t));
        }else{
            int m;
            cin >> m;
            querys.emplace_back(vector<int>{com, m});
        }
    }

    sort(vec.begin(), vec.end(), [](auto a, auto b){
        if(a.first != b.first){
            return (a > b);
        }else{
            return (a < b);
        }
    });

    map<pair<int, int>, int> mp; 
    Umap<int, pair<int, int> > mp2;
    int cnt = 0;

    for(auto&& e : vec){
        mp[e] = cnt;
        mp2[cnt] = e;
        ++cnt;
    }

    point.assign(n + 1, 0);
    int siz = mp.size();

    Set<int> s;

    for(int i = 1; i <= n; ++i){
        s.insert(mp[make_pair(point[i], i)]);
    }

    for(auto &&e : querys){
        if(e.front() == 0){
            int t = e[1];
            int p = e[2];
            s.erase(mp[make_pair(point[t], t)]);
            point[t] += p;
            s.insert(mp[make_pair(point[t], t)]);
        }else{
            int m = e[1];
            int pos = *(s.find_by_order(m-1));
            cout << mp2[pos].second << ' ' << mp2[pos].first << '\n';
        }
    }

    return (0);
}


Measured memory_bytes: 49488
#include <iostream>
using namespace std;
 
    
    
int main(){
    string s,t,u;
    int a,b;

    cin>>s>>t;
    cin>>a>>b;
    cin>>u;

    if (u==s)
    {
        a=a-1;
    }
    else
    {
        b=b-1;
    }
    
    
    cout<<a<<" "<<b<<endl;

    return 0;
}

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

using namespace std;

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

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int f(ll x){
  int ret = 0;
  while(x){
    ret += x%10;
    x /= 10;
  }
  return ret;
}

int main(){
  ll n;
  cin>>n;
  int ans = 0;
  ll b = 1;
  while(b<=n){
    CHMAX(ans, f(n));
    int c = (n/b)%10;
    if(c>0){
      n = ((n/b)-1)*b + (b-1);
    }
    b *= 10;
    // DEBUG(n);
  }
  CHMAX(ans, f(n));
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 256
## coding: UTF-8
from decimal import *
#import math

A, B = map(str,input().split())
#A = int(A)
#B = float(B)
#print(A, B)
#print(A%10)

#print(math.floor(A*B))
#print(A*B//1)

A = Decimal(A)
B = Decimal(B)
C = A*B
#print(C)
#print(type(C))
print(int(C))
'''
b = int(B[0])
c = int(B[2])
d = int(B[3])

print(b, c, d)
'''

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

int main(){
    ll h, w;
    cin >> h >> w;
    if(h == 1 || w == 1){
        cout << 1 << "\n";
    } else {
        cout << (h * w + 1) / 2 << "\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <ctime>
#include <algorithm>
#define N 201000
typedef long long ll;
template <typename T> inline void read(T &x) {
	x = 0; char c = getchar(); bool flag = false;
	while (!isdigit(c)) { if (c == '-')	flag = true; c = getchar(); }
	while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
	if (flag)	x = -x;
}
using namespace std;
const int P = 1e9 + 7;
const int inf = 987654321;
inline void MIN(int &a, int b) {
	if (b < a)	a = b;
}
int n, m;
char s[N];
namespace jzp1 {
	ll jie[N], jieni[N];
	inline ll get_c(int n, int m) {
		if (n < 0 || m < 0 || n - m < 0)	return 0;
		return jie[n] * jieni[m] % P * jieni[n - m] % P;
	}
	inline ll quickpow(ll x, int k) {
		ll res = 1;
		while (k) {
			if (k & 1)	res = res * x % P;
			x = x * x % P;
			k >>= 1;
		}
		return res;
	}
	inline void sol() {
		if (n == 1) { puts("1"); return ; }
		jie[0] = jieni[0] = 1;
		int up = n + 1;
		for (int i = 1; i <= up; ++i)	jie[i] = jie[i - 1] * i % P;
		jieni[up] = quickpow(jie[up], P - 2);
		for (int i = up - 1; i; --i)	jieni[i] = jieni[i + 1] * (i + 1) % P;
		ll res = 0;
		for (int i = 0; i <= n; ++i) {
			res = (res + get_c(n - i + 1, i) - get_c(n - i - 1, i - 2)) % P;
		}
		printf("%lld\n", (res % P + P) % P);
	}
}
ll f[N];
ll sum[N];
int main() {
	read(n), read(m);
	scanf("%s", s + 1);
	bool flag = false;
	int tmp = 0;
	for (int i = 1; i <= m; ++i)	if (s[i] != s[1]) { flag = true; tmp = i - 1; break; }
	if (!flag) { jzp1::sol(); return 0; }
	if (n & 1) { puts("0"); return 0; }
	int lst = 1, mn = tmp | 1;
	for (int i = 2; i <= m; ++i) {
		if (s[i] != s[1]) {
			if (lst & 1)	MIN(mn, lst);
			lst = 0;
			continue;
		}
		if (s[i] == s[i - 1])	++lst;
		else {
			if (lst & 1) MIN(mn, lst);
			lst = 1;
		}
	}
	n >>= 1;
	int k = (mn + 1) >> 1;
	MIN(k, n);
	f[0] = 1; sum[0] = 1;
	for (int i = 1; i <= n; ++i) {
		if (i <= k)	f[i] = sum[i - 1];
		else f[i] = (sum[i - 1] - sum[i - k - 1]) % P;
		sum[i] = (sum[i - 1] + f[i]) % P;
	}
	ll ans = 0;
	for (int i = 1; i <= k; ++i) {
		ans = (ans + f[n - i] * i) % P;
	}
	ans = (ans << 1) % P;
	printf("%lld\n", (ans % P + P) % P);
	return 0;
}

/*
3 3
BBB
//4

1 1
B
//1

12 10
RRRRBRRRRB
//78

6 5
RRBBR
//8
*/

Measured memory_bytes: 6516
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
HALF = sum(As)/2

from itertools import accumulate
from bisect import bisect_left
cum = list(accumulate(As))
idx = bisect_left(cum, HALF)
L = abs(sum(As[:idx])-sum(As[idx:]))
R = abs(sum(As[:idx+1])-sum(As[idx+1:]))
print(min(L, R))

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

using namespace std;
long long dp[2009];
int MOD=1e9+7;
int s=0;
long long solve(int cu){
if(cu==0)return 1;
long long &ans=dp[cu];
if(ans!=-1)return ans;
ans=0;

for(int i=3;i<=cu;i++)ans=(ans%MOD+solve(cu-i)%MOD)%MOD;


return ans%MOD;
}
int main(){
cin>>s;
memset(dp,-1,sizeof dp);
long long ans=solve(s);
cout<<ans;


    return 0;
}


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

typedef long long ll;

long long n,m,v,p;

int main(int argc, char const *argv[])
{
    scanf("%lld %lld %lld %lld",&n,&m,&v,&p);
    vector<ll> a(n);
    for(int i = 0;i < n;i++)scanf("%lld",&a[i]);
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());

    int l = 0,r = n;
    for (int i = 0; i < 100; ++i)
    {
        int x = (l+r)/2;
        long long B = 0;//投票してもいい票の総数
        bool ok;

        //0,...,p-2までは投票してOK
        if(x <= p-1)ok = true;
        else if(a[x]+m < a[p-1])ok = false;
        else{
            B += (p+n-1-x)*m;
            for(int j = p-1;j <= x-1;j++){
                B += (a[x] + m - a[j]);
            }
            ok = (B >= m*v);
        }
        if(ok)l = x;else r = x;
    }
    cout << l+1 << endl;
    
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
    for (T &x : vec)
        is >> x;
    return is;
}

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

    vector<int> A(n);
    cin >> A;

    ll sum=0;

    vector<int> B(n);

    REP(i,n){
        B[i] = A[i] - i - 1;
    }

    sort(B.begin(), B.end());

    ll median = B[n/2];

    REP(i,n){
        sum+=abs(B[i]-median);
    }

    cout << sum << endl;

    return 0;
}

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

using namespace std;

int main(){
  int n,q;
  cin>>n>>q;
  int c[300000];
  for(int i=0;i<n;i++){
    cin>>c[i];
  }
  sort(begin(c),begin(c)+n);
  while(q--){
    int qq;
    cin>>qq;
    int m=0;
    for(int i=qq;i-qq<=300000;i+=qq){
      auto it=lower_bound(begin(c),begin(c)+n,i);
      if(it!=begin(c)){
	m=max(m,it[-1]%qq);
      }
    }
    cout<<m<<endl;
  }
}

Measured memory_bytes: 2344
#include<stdio.h>
int main()
{
	int n,x,l[100],i=0,d=0;

	scanf("%d%d",&n,&x);
	for(i=0;i<n;i++)
		scanf("%d",&l[i]);
	i=0;
	while(1){
		d+=l[i];
		if(d<=x)
			i++;
		else
			break;
	}
	if(n>=i){
		printf("%d",i+1);
		return 0;
	}
	else{
		printf("%d",n+1);
		return 0;
	}
}

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

int main() {
  int N;
  cin >> N;
  cout << (N/2)+(N%2) << endl;
  return 0;
}

Measured memory_bytes: 256
// #define _CRT_SECURE_NO_WARNINGS
// #define _USE_MATH_DEFINES	// M_PI=3.1415...
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
#include <iomanip>	// 20桁出力 cout << setprecision(20) << double;
#include <queue>
#include <bitset>	// bitset<8> bs1(131uL); // 10000011 bs1[0]は1 01stringからビット集合生成可
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VL;
typedef map<int, int> MAPII;
typedef multimap<int, char, greater<int> > MuMAPIC;
typedef vector<pair<int, int> > VPII;
typedef multimap<int, string, greater<int> > MuMIS;
typedef pair<int, int> P;
typedef pair<int, pair<P, P> > PP;

#define MP make_pair
#define FAST_IO  cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FOR_REV(i,a,b) for(int i=(a);i>=(b);i--)
//for gcc (未test)
// #define FOREACH_IT(it,c) for(typeof(c)::iterator it=(c).begin(); it!=(c).end(); ++it)
//for Visual Studio
#define foreach_it(type,it,c) for(type::iterator it=c.begin(),c_end=c.end();it!=c_end;++it)
// for Debug.
#define DUMP_VVI(b) FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}
#define D_OUT(str,value) if(dbgF){cout<<str<<" : "<<value<<endl;}
// 入力をpush_back(d)やarray[d]に使う時に1行で書ける
// int INPUT_INT() {int d;cin>>d;return d;}
template<class T>T IN() { T d; cin >> d; return d; }
// 最大公約数（Greatest Common Divisor）
LL gcd(LL a, LL b) { return (b > 0) ? gcd(b, a%b) : a; }
// 最小公倍数（Least Common Multiple）
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
// Y年はうるう年か否か
bool uruu(LL Y) { return (((Y % 4 == 0 && Y % 100 != 0) || Y % 400 == 0) ? true : false); }

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

// vector注意
// vec[i][j]の形に入力を入れるとき、vecは初期化してある必要がある.

// ------------------- include, typedef, define END. -------------------


int main() {
	FAST_IO;
	// for D_OUT(str, value)  ... cout<< str <<" : "<< value <<endl;
	bool dbgF = true;

	//コードはここから書く.

	int N, L;
	vector<string> s;
	cin >> N >> L;
	FOR(i, 0, N)
		s.push_back(IN<string>());
	
	sort(s.begin(), s.end());
	FOR(i, 0, N)
		cout << s[i];
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
from operator import itemgetter
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}


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

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

lst1 = []

fac = [0]
for i in range(n-1):
    fac.append(fac[-1]+(i+1))

ans = []
res = fac[n-1]
ans.append(res)

lst1 = [list(map(int,readline().split())) for i in range(m)]
lst1.reverse()
for i in range(m):
    a,b = lst1[i][0],lst1[i][1]
    a,b = a-1,b-1
    if not same(a,b):
        res -= size(a)*size(b)
        unite(a,b)
    ans.append(res)

for i in range(len(ans)-2,-1,-1):
    print(ans[i])
         






Measured memory_bytes: 102108
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;
int main() {
	bool f[26] = {};
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++)f[s[i] - 'a'] = 1;
	for (int i = 0; i < 26; i++) {
		if (!f[i]) {
			char a = 'a' + i;
			cout << a << endl;
			return 0;
		}
	}
	cout << "None" << endl;
	return 0;
}


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

using namespace std;
static const int MAX_N = 1 << 17;
int bit[MAX_N + 1];
int n;


int sum(int i)
{
	int s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}
	return(s);
}

void add(int i, int x)
{
	while (i <= n)
	{
		bit[i] += x;
		i += i & -i;
	}
}

void solve()
{
	int q;
	cin >> n >> q;
	for (int i = 0; i < q; ++i)
	{
		int com, x, y;
		scanf("%d%d%d", &com, &x, &y);
//		cin >> com >> x >> y;
		if (com == 0)
		{
			add(x, y);
		}
		else
		{
			printf("%d\n", sum(y) - sum(x - 1));
//			cout << sum(y) - sum(x - 1) << endl;
		}
	}
}

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

Measured memory_bytes: 1620
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M,sum=0;
  cin >> N >> M;
  int A[M];
  for(int i = 0; i < M; i++){
    int a;
    cin >> a;
    sum += a;
  }
  int c = N - sum;
  if(c < 0) cout << -1 << endl;
  else cout << c << endl;
}

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

using namespace std;
typedef long long ll;

ll N,M;
ll a[100];
ll b[100];

struct UnionFind{
    vector<ll> par;
    vector<ll> chs;
    UnionFind(ll N){
        par.resize(N);
        chs.resize(N);
        for(int i=0;i<N;i++) par[i] = i;
        for(int i=0;i<N;i++) chs[i] = 1;
    }
    ll root(ll n){
        if(par[n] == n) return n;
        return root(par[n]);
    }
    void unite(ll a, ll b){
        ll ra = root(a);
        ll rb = root(b);
        if(ra == rb) return;
        if(chs[ra] >= chs[rb]){
            par[rb] = ra;
            chs[ra] = max(chs[ra], chs[rb] + 1);
        }else{
            par[ra] = rb;
        }
    }
    bool isSame(ll a,ll b){
        return root(a) == root(b);
    }
};

int main(){
    cin >> N >> M;
    for(int i=0;i<M;i++) cin >> a[i] >> b[i];
    for(int i=0;i<M;i++) a[i]--,b[i]--;
    ll sum = 0;
    for(int i=0;i<M;i++){
        UnionFind uf = UnionFind(N);
        for(int j=0;j<M;j++){
            if(i==j) continue;
            uf.unite(a[j], b[j]);
        }
        bool f = false;
        ll r = uf.root(0);
        for(int i=1;i<N;i++){
            if(r != uf.root(i)) f = true;
        }
        if(f) sum++;
    }
    cout << sum << endl;
    return 0;
}

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

int main(){
    int a, b; cin >> a >> b;
    string A = "";
    string B = "";
    for(int i = 0; i < a; i++){
        A += to_string(b);
    }
    for(int i = 0; i < b; i++){
        B += to_string(a);
    } 
    if(A <= B){
        cout << A << endl;
    } else{
        cout << B << endl;
    }
    return 0;
}

Measured memory_bytes: 256
H, W, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

from itertools import product

S = [set() for _ in range(10)]
# S[i]: set(黒いマスをi個こ含む3*3マスの中心セル)

for a,b in AB:
  for x,y in product([-1,0,1], repeat=2):
    X = a+x-1
    Y = b+y-1
    if X<=0 or H-1<=X or Y<=0 or W-1<=Y:
      continue
    for i in range(10):
      if (X, Y) in S[i]:
        S[i].remove((X, Y))
        S[i+1].add((X, Y))
        break
    else:
      S[1].add((X, Y))

L = [len(s) for s in S[1:]]
print((H-2)*(W-2) - sum(L))

for l in L:
  print(l)

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

using ll    = long long;
using ull   = unsigned long long;
using veci  = vector<int>;
using vecll = vector<ll>;
#define EPS (1e-7)
#define INF (1e9)
#define PI  (acos(-1))
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define REP(i,n) for(int i= 0;i<(int)(n);++i)
#define pb push_back

veci enum_div(int n){
	veci ret;
	ret.pb(1);
	for(int i=1;i*i<n;i++){
		if(n%i==0){
			ret.pb(i);
			if(i != n/i){ret.pb(n/i);}
		}
	}
	ret.pb(n);
	return ret;
}
int gcb(int a,int b){return ((b == 0)? a : gcb(b,a%b));}
int gcd(int a,int b){return (a*b) / gcb(a,b);}

int main(){
    char c;
    string s = "aeiou";
    cin >> c;
    REP(i,s.size()){
        if(c == s[i]){
            cout << "vowel" << endl;
            return 0;
        }
    }
    cout << "consonant" <<endl;
    return 0;
}



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

int power(int a,int b)
{
    int res=1;
    while(b>0){
        if(b&1)
            res*=a;
        b>>=1;
        a*=a;
    }
    return res;
}

int main()
{
    int n;
    string s;
    cin>>s;
    map<int,int> mp;
    for(int i=0;i<s.length();i++){
        mp[(int)s[i]]++;
    }
    int c=0,ans=0;
    for(int i=65;i<=90;i++)
        if(mp[i]>0 && mp[i]==2) {c++;}
    if(c==2) cout<<"Yes"<<'\n';
    else
        cout<<"No"<<'\n';
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int a,b,c,i;
    int A[2],B[2],C[2];
    while(1){
        scanf("%d %d %d",&a,&b,&c);
        if(a==-1&&b==-1&&c==-1)break;
        b=b+a*60;
        C[0]=7200-(c+b*60);
        C[1]=C[0]*3;
        for(i=0;i<2;i++){
            B[i]=C[i]/60;
            C[i]=C[i]%60;
            A[i]=B[i]/60;
            B[i]=B[i]%60;
            printf("%02d:%02d:%02d\n",A[i],B[i],C[i]);
        }
    }
    return 0;
}

Measured memory_bytes: 612
class Factorial:
    def __init__(self,n,mod):
        self.f=f=[0]*(n+1)
        f[0]=b=1
        self.mod=mod
        for i in range(1,n+1):f[i]=b=b*i%mod
        self.inv=inv=[0]*(n+1)
        inv[0]=b=pow(self.f[n],mod-2,mod)
        for i in range(1,n+1):inv[i]=b=b*(n+1-i)%mod
        self.inv.reverse()
    def factorial(self,i):
        return self.f[i]
    def ifactorial(self,i):
        return self.inv[i]
    def comb(self,n,k):
        return self.f[n]*self.inv[n-k]%self.mod*self.inv[k]%self.mod if n>=k else 0
M=10**9+7
a,b,c,d=map(int,input().split())
comb=Factorial(c+d+2,M).comb
f=lambda r,c:comb(c+r+2,r+1)-c-r-2
print((f(c,d)-f(c,b-1)-f(a-1,d)+f(a-1,b-1))%M)

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }
  sort(a.begin(), a.end(), greater<int>());

  int s1 = 0, s2 = 0;
  for (int i = 0; i < N; i++) {
    if (i % 2) {
      s2 += a.at(i);
    } else {
      s1 += a.at(i);
    }
  }
  cout << (s1 - s2) << endl;
}

Measured memory_bytes: 256
N, X = map(int, input().split())


def func(X, Y):
    if X < Y:
        return func(Y, X)
    # X>=Y
    if X % Y == 0:
        return 2*X-Y
    else:
        return 2*Y*(X//Y) + func(Y, X % Y)


ans = N + func(X, N-X)

print(ans)

Measured memory_bytes: 61884