akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC129
{
	class Program
	{
		static void Main(string[] args)
		{
			var NM = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
			var k = new bool[NM[0]];
			foreach (var a in ReadLines(NM[1]).Select(n => int.Parse(n) - 1)) { k[a] = true; }
			var ans = k.Aggregate(new int[] { 0, 1 }, (p, a) => a ? new int[] { p[1], 0 } : new int[] { p[1], (p[0] + p[1]) % 1000000007 });
			Console.WriteLine(ans[1]);
		}

		static IEnumerable<string> ReadLines(int n) => Enumerable.Range(0, n).Select(_ => Console.ReadLine());
	}
}


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

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int, int> pii;

const int INF = 1 << 29;
const double EPS = 1e-10;

double zero(double d) {
    return d < EPS ? 0.0 : d;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    os << '[';
    rep(i, a.size()) os << (i ? " " : "") << a[i];
    return os << ']';
}

// to avoid error on mingw
string toString(int i) {
    stringstream ss;
    ss << i;
    return ss.str();
}

const int M = 1000000007;
// a^k
ll fpow(ll a, ll k, int M) {
    ll res = 1ll;
    ll x = a;
    while (k != 0) {
        if ((k & 1) == 1)
            res = (res * x) % M;
        x = (x * x) % M;
        k >>= 1;
    }
    return res;
}

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


int main() {
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(8);
    ios_base::sync_with_stdio(false);

    int H,W,N;
    cin >> H >> W >> N;

    int a[H][W];
    memset(a, 0, sizeof(a));
    int vis[H][W];
    memset(vis, -1, sizeof(vis));

    int start = 0;
    rep(r,H) {
        string t;
        cin >> t;
        rep(c,W) {
            if(t[c] == 'S')
                start = r*W + c;
            else if(t[c] == 'X')
                a[r][c] = -1;
            else if(t[c] != '.')
                a[r][c] = t[c] - '0';
        }
    }


    int ans = 0;

    REP(target,1,N+1) {
        queue<int> que;
        que.push(start);

        memset(vis, -1, sizeof(vis));
        vis[start / W][start % W] = 0;

        while (!que.empty()) {
            int t = que.front(); que.pop();
            int r = t / W;
            int c = t % W;

            if (a[r][c] == target) {
                ans += vis[r][c];
                start = r * W + c;
                break;
            }

            rep(i, 4) {
                int nr = r + dy[i];
                int nc = c + dx[i];

                if (nr < 0 || H <= nr || nc < 0 || W <= nc
                    || a[nr][nc] == -1 || vis[nr][nc] != -1)
                    continue;

                vis[nr][nc] = vis[r][c] + 1;
                que.push(nr * W + nc);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 9052
#include<stdio.h>

int chara[10000],n;

int search(int num,int color){
	int s,e,sum,total,p;
	s=num;
	e=num;
	sum=1;
	total=0;
	while(1){
		do{
			p=sum;
		if(s>0){
			if(chara[s-1]==color){
				s--;
				sum++;
			}
		}
		if(e<n-1){
			if(chara[e+1]==color){
				e++;
				sum++;
			}
		}
		}while(sum-p>0);
		if(sum<4) break;
		total+=sum;
		if(s==0 || e==n-1) break;
		if(chara[s-1]!=chara[e+1]) break;
		color=chara[s-1];
		sum=0;
	}
	return total;
}

int main(){
	int i,max,a;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<n;i++){
			scanf("%d",&chara[i]);
			chara[i]--;
		}
		max=0;
		for(i=0;i<n;i++){
			a=search(i,(chara[i]+1)%3);
			max=(a>max)?a:max;
			a=search(i,(chara[i]+2)%3);
			max=(a>max)?a:max;
		}
		printf("%d\n",n-max);
	}
	return 0;
}

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

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

using namespace std;

int main()
{
  string s;
  cin >> s;
  int result = 0;
  REP(i,s.length()) {
    int tmp = 0;
    FOR(j, i, s.length()) {
      if (s[j] == 'A' || s[j] == 'T' || s[j] == 'C' || s[j] == 'G') {
        tmp++;
      } else {
        break;
      }
    }
    result = max(result, tmp);
  }

  cout << result << endl;
}


Measured memory_bytes: 256
l, r = list(map(int,input().split()))

if r - l >= 2019:
  print(0)
  
else:
  ll = l % 2019
  rr = r % 2019
  if rr < ll:
    print(0)
    
  else:
    keep = 2020
    for i in range(ll, rr+1):
      for j in range(i+1, rr+1):
        keep = min((i*j)%2019, keep)
    print(keep)

Measured memory_bytes: 3060
n,q = map(int,input().split())
s = input()
word = list(s)
li = [list(input().split()) for _ in range(q)]
memo = {}

def dfs(m):
    k = m
    if m in memo:
        return memo[m]
    for x in li:
        if word[m] == x[0]:
            if x[1] == 'R':
                m += 1
            else:
                m -= 1
        if m < 0:
            memo[k] = 'Left'
            return 'Left'
        elif m > n-1:
            memo[k] = 'Right'
            return  'Right'
    memo[k] = True
    return True

def left(a,b):
    m = int((a+b)/2)
    if a == m:
        return b
    if dfs(m) == 'Left':
        return left(m,b)
    else:
        return left(a,m)

def right(a,b):
    m = int((a+b)/2)
    if a == m:
        return a
    if dfs(m) == 'Right':
        return right(a,m)
    else:
        return right(m,b)

if dfs(0) == 'Right':
    print(0)
elif dfs(0) == 'Left':
    if dfs(n-1) == 'Right':
        print(right(0,n-1) - left(0,n-1) + 1)
    elif dfs(n-1) == 'Left':
        print(0)
    else:
        print(n - left(0,n-1))
else:
    if dfs(b) == 'Right':
        print(right(0,n-1) + 1)
    elif dfs(b) == 'Left':
        print(0)
    else:
        print(n)


Measured memory_bytes: 29172
// *INDENT-OFF*
#pragma GCC optimize("-O3")
#include <bits/stdc++.h>
using namespace std;typedef long long ll;typedef pair<int, int>pii;typedef pair<ll, int>pli;typedef pair<ll,ll>pll;typedef pair<double,double>pdd;typedef long double ld;
pll exgcd(const ll x,const ll y){if(!y)return{1,0};pll cur=exgcd(y,x%y);return {cur.second,cur.first-(x/y)*cur.second};}
template<typename T>ostream &operator<<(ostream &out,const vector<T>&vec){const int n=vec.size();out<<'[';for(int i=0;i<n;i++)out<<vec[i]<<(i==n-1?"":", ");out<<']';return out;}
template<typename T,typename U>ostream &operator<<(ostream&out,const pair<T,U>&p){out<<'<'<<p.first<<", "<<p.second<<'>';return out;}
const ll __mod__=998244353ll;ll mod(ll x,ll p=__mod__){return((x%p)+p)%p;}ll mmod(){return 1ll;}ll fpow(ll a,ll b,ll m){ll ans=1ll;for(a%=m;b;a=a*a%m,b>>=1)if(b&1)ans=ans*a%m;return ans;}
template<typename...U>ll mmod(const ll&hd,const U&...tl){return mod((hd%__mod__)*mmod(tl...),__mod__);}
void print(){cout<<"\n";}template<typename T,typename...U>void print(const T&hd,const U&...tl){cout<<hd<<(sizeof...(tl)?" ":"");print(tl...);}
inline ll fmul(ll a,ll b,ll m){ll d=(ll)floor(a*(ld)b/m+0.5);ll r=(a*b-d*m)%m;if(r<0)r+=m;return r;}void Main();
#ifdef ConanYu
void err(){cerr<<"\n";}template<typename T,typename...U>void err(const T&hd,const U&...tl){cerr<<hd<<(sizeof...(tl)?", ":"");err(tl...);}
#define debug(x...) {cerr<<""#x" = ";err(x);}
#else
#define debug(...) 0
#endif
#define SZ(o) (int(o.size()))
#define all(o) o.begin(), o.end()
int main() {
#ifdef ConanYu
  clock_t clock_start = clock();assert(freopen("test.txt", "r", stdin));
#else
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
  int T = 1;
  // cin >> T;
  while(T--) Main();
#ifdef ConanYu
  cerr << "time: " << ((clock() - clock_start) * 1.0 / CLOCKS_PER_SEC) << "\n";
#endif
  return 0; }
// *INDENT-ON*
// ********************************************************************************************************

void Main() {
  int n, l;
  cin >> n >> l;
  int mn = INT_MAX;
  int ans = 0;
  for(int i = 0; i < n; i++) {
    const int cur = l + i;
    ans += cur;
    mn = min(abs(cur), mn);
  }
  debug(mn);
  for(int i = 0; i < n; i++) {
    if(abs(l + i) == mn) {
      ans -= l + i;
      break;
    }
  }
  print(ans);
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> plint;
typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }
const lint MOD = 1e9 + 7, INF = 1e18;


lint D;
lint decrease[26];
lint satis[365][26];
lint last[26];

lint downscore(lint passed) {
	lint sum = 0;
	REP(i, 26) {
		sum += decrease[i] * (passed - last[i]);
	}
	return -sum;
}

int main() {
	cin >> D;
	REP(i, 26) {
		cin >> decrease[i];
	}
	REP(i, D) {
		REP(j, 26) {
			cin >> satis[i][j];
		}
	}

	lint score = 0;
	REP(i, D) {
		lint maxv = -INF, max_idx = -1;
		REP(s, 26) {
			lint inst = 0;
			inst += satis[i][s];
			inst += downscore(i + 1);
			chmax(inst, 0ll);
			if (maxv < inst) {
				maxv = inst;
				max_idx = s;
			}
		}
		last[max_idx] = i + 1;
		cout << 10;
		if (i != D - 1) cout << endl;
	}
}


Measured memory_bytes: 3716
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
using namespace std ;
int main(){
    int n, k;
    int tmp;
    int flag = 0;
    cin >> n >> k;
    
    vector<int> v;
    int i, d;
    
    for(i = 0; i < k; i++){
        cin >> d;
        v.push_back(d);
    }
    
while(1){
        tmp = n;
        flag = 0;
        while(tmp != 0){
            for(i = 0; i < k; i++){
                if(tmp%10 == v[i]){
                    flag = 1;
                    break;
                }
            }	
            if(flag){
                break;
            }else{
                tmp /= 10;
            }
        }
        if(flag == 0){
            cout << n << endl;
            return 0;
        }
        n++;
    }
}


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

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

  vector<vector<int>> A(2, vector<int>(N));
  rep(i, 2) rep(j, N) cin >> A[i][j];

  int ans = 0;
  rep(n, N) {
    int sum = 0;
    for (int j = 0; j <= n; j++)
      sum += A[0][j];
    for (int j = n; j < N; j++)
      sum += A[1][j];
    ans = max(ans, sum);
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 5;
ll a[N];
int main()
{
    int n;
    while(cin >> n){
		for(int i = 1; i <= n; i++)
			scanf("%lld",&a[i]);
		int maxn = 0;
		int ans = 0;
		for(int i = 1; i < n; i++){
			if(a[i] >= a[i+1]){
				ans++;
				if(ans > maxn){
					maxn = ans;
				}
			}else{
				ans = 0;
			}
		}
        cout << maxn << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
N = int(input())
S = input()

ans = 0

for i in range(10):
    if str(i) not in S:
        continue
    ind_i = S.index(str(i))
    for j in range(10):
        if str(j) not in S[ind_i+1:]:
            continue
        ind_j = S[ind_i+1:].index(str(j)) + ind_i+1
        for k in range(10):
            if str(k) in S[ind_j+1:]:
                ans += 1

print(ans)


Measured memory_bytes: 3060
n,k = map(int, input().split())
a = list(map(int, input().split()))
number = [0]*n
for i in range(n):
    number[a[i]-1]+=1
number.sort(reverse=True)
ans = 0

for i in range(k):
    ans += number[i]
ans = n-ans
print(ans)

Measured memory_bytes: 25780
#include <stdio.h>

int main()
{
  int v,i,j,N;
  int A[1000];

  scanf("%d",&N);

  if(N < 1 || N > 100) return 0;

  for( i = 0 ; i < N ; i++ )
    {
      scanf("%d",&A[i]);
    }
  
  for( j = 0 ; j < N ; j++ )
    {
      if(j == N-1) printf("%d",A[j]);
      else printf("%d ",A[j]);
    }
  printf("\n");

  for( i = 1 ; i <= N-1 ; i++ )
    {
      v = A[i];
      j = i - 1;

      while(j >= 0 && A[j] > v)
	{
	  A[j+1] = A[j];
	  j--;
	}
      A[j+1] = v;

      for( j = 0 ; j < N ; j++ )
	{
	  if(j == N-1) printf("%d",A[j]);
	  else printf("%d ",A[j]);
	}
      printf("\n");
    }

  
  return 0;
}



Measured memory_bytes: 2080
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
const int MOD = INF+7;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))
#define rrep(i,N) for(int (i)=(N-1);(i)>0;--i)
#define FOR(i,j,N) for(int (i)=(j);(i)<(N);++(i))
#define put(n) cout<<(n)<<endl;
#define rall(v) v.rbegin(),v.rend()
#define MP make_pair
#define pb(n) push_back(n)
#define int long long
using P = pair<int,int>;
signed main(){
    int N;
    cin >> N;
    vector<int> A(N),B(N);
    int sum_A = 0,sum_B = 0;
    rep(i,N){
        cin >> A[i] >> B[i];
    }

    int taka = 0;
    int aoki = 0;

    vector<P> dish(N);
    rep(i,N) dish[i] = {A[i]+B[i],i};
    sort(rall(dish));
    rep(i,N){
        if(i%2 == 0) taka += A[dish[i].second];
        else aoki += B[dish[i].second];
    }
    cout << taka - aoki << endl;
}

Measured memory_bytes: 3328
# -*- coding: utf-8 -*-
import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
r = range

x, y, z = map(int, input().split())

ret = 0
while not(x % 2 == 1 or y % 2 == 1 or z % 2 == 1):
    ret += 1
    x, y, z = y//2+z//2, z//2+x//2, x//2+y//2
    if ret > 10000:
        ret = -1
        break;

print(ret)

Measured memory_bytes: 12400
# import sys
# read = sys.stdin.buffer.read
# readline = sys.stdin.buffer.readline
# readlines = sys.stdin.buffer.readlines

# def myinput():
#     return map(int,readline().split())

s = input()
l = len(s)
ans = 0

for i in range(2**(l-1)):
    temp = s[0]
    for j in range(l-1):
        if i & (2**j):
            ans += int(temp)
            temp = s[j+1]
        else:
            temp += s[j+1]
    ans += int(temp)

print(ans)

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

int cnt[100002];
int main() {
	int n; scanf("%d", &n);
	rep(i, n) {
		int a, b;
		scanf("%d%d", &a, &b);
		cnt[a - 1]++; cnt[b]--;
	}
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		if (i)cnt[i] += cnt[i - 1];
		if (cnt[i] >= i)ans = i;
	}
	printf("%d\n", ans);
}

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

#define N 500001

class Node {
    public:
        int location;
        int l, r;
        Node() {}
};

class Point {
    public:
        int id, x, y;
        Point() {}
        Point(int id, int x, int y): id(id), x(x), y(y) {}
        bool operator < (const Point &p) const {
            return id < p.id;
        }
        
        void print() {
            printf("%d\n", id);
        }
};

Point P[N];
Node T[N];
int np;
vector<Point> ans;
int NIL = -1;

bool lessX(const Point &p1, const Point &p2) {
    return p1.x < p2.x;
}
bool lessY(const Point &p1, const Point &p2) {
    return p1.y < p2.y;
}

int buildKDtree(int l, int r, int depth) {
    if (l >= r) {
        return NIL;
    }

    int mid = (l + r) / 2;
    if (depth % 2 == 0) {
        sort(P + l, P + r, lessX);
    } else {
        sort(P + l, P + r, lessY);
    }

    int t = np++;
    T[t].location = mid;
    T[t].l = buildKDtree(l, mid, depth + 1);
    T[t].r = buildKDtree(mid + 1, r, depth + 1);
    
    return t;
}

void find(int v, int sx, int tx, int sy, int ty, int depth) {
    int x = P[T[v].location].x;
    int y = P[T[v].location].y;

    if (x >= sx && x <= tx && y >= sy && y <= ty) {
        ans.push_back(P[T[v].location]);
    }

    if (depth % 2 == 0) {
        if (T[v].l != NIL) {
            if (x >= sx) {
                find(T[v].l, sx, tx, sy, ty, depth + 1);
            }
        }

        if (T[v].r != NIL) {
            if (x <= tx) {
                find(T[v].r, sx, tx, sy, ty, depth + 1);
            }
        }
    } else {
        if (T[v].l != NIL) {
            if (y >= sy) {
                find(T[v].l, sx, tx, sy, ty, depth + 1);
            }
        }

        if (T[v].r != NIL) {
            if (y <= ty) {
                find(T[v].r, sx, tx, sy, ty, depth + 1);
            }
        }
    }
}

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

    np = 0;

    int id, x, y;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &x, &y);
        P[i] = Point(i, x, y);
    }

    buildKDtree(0, n, 0);

    cin >> q;
    int sx, tx, sy, ty;
    for (int i = 0; i < q; i++) {
        ans.clear();
        scanf("%d %d %d %d", &sx, &tx, &sy, &ty);
        find(0, sx, tx, sy, ty, 0);
        sort(ans.begin(), ans.end());
        for (int j = 0; j < ans.size(); j++) {
            ans[j].print();
        }
        printf("\n");
    }

    return 0;
}



Measured memory_bytes: 14548
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <string>
 
using namespace std;
 
void solve();
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}
 
void solve() {
    int n;
    cin >> n;
    int a[2][n];
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    int ma = 0;
    for(int i = 0; i < n; i++) {
        bool now = false;
        int  sum = 0;
        for(int j = 0; j < n; j++) {
            if(!now) sum += a[0][j];
            if(now) sum += a[1][j];
            if(i == j) {
                now = true;
                sum += a[1][j];
            }
        }
        ma = max(ma,sum);
    }
    cout << ma << endl;
    

}

Measured memory_bytes: 256
local x,y,a,b,c=io.read("n","n","n","n","n")
local t={}
for i=1,a do
    table.insert(t,{io.read("n"),"a"})
end
for i=1,b do
    table.insert(t,{io.read("n"),"b"})
end
for i=1,c do
    table.insert(t,{io.read("n"),"c"})
end
table.sort(t,function(a,b)
    return a[1]<b[1]
end)

local max=0
local aounter=0
local bounter=0
local counter=0
for i=a+b+c,1,-1 do
    if aounter<x and t[i][2]=="a" then
        aounter=aounter+1
        max=max+t[i][1]
    end
    if bounter<y and t[i][2]=="b" then
        bounter=bounter+1
        max=max+t[i][1]
    end
    if aounter+bounter+counter<x+y and t[i][2]=="c" then
        counter=counter+1
        max=max+t[i][1]
    end
    if aounter+bounter+counter==x+y or aounter+bounter==x+y then
        break
    end
end
print(string.format("%d",max))

Measured memory_bytes: 25352
from functools import reduce

n = int(input())
values = list(map(int, list(input().split())))

def mymin(a, b):
    if a < b:
        return a
    else:
        return b

def mymax(a, b):
    if b < a:
        return a
    else:
        return b

def mysum(a, b):
    return a + b

print(reduce(mymin, values), reduce(mymax, values), reduce(mysum, values))\


Measured memory_bytes: 7268
import itertools as it
import collections as cl
N = int(input())
a = list(map(int,input().split()))
acc = [0]+list(it.accumulate(a))
d = cl.defaultdict(int)
for i in range(len(acc)):
    d[acc[i]] += 1
ans = 0
for v in d.values():
    ans += v*(v-1)//2
print(ans)

Measured memory_bytes: 41984
import itertools
H, W, M, *HW = [int(_) for _ in open(0).read().split()]
H += 1
W += 1
cnth = [0] * H
cntw = [0] * W
se = set((h, w) for h, w in zip(HW[::2], HW[1::2]))
for h in HW[::2]:
    cnth[h] += 1
maxcnth = max(cnth)
for w in HW[1::2]:
    cntw[w] += 1
maxcntw = max(cntw)
candidxh = [idxh for idxh, c in enumerate(cnth) if c == maxcnth]
candidxw = [idxw for idxw, c in enumerate(cntw) if c == maxcntw]
ans = maxcnth + maxcntw
for idxh, idxw in itertools.product(candidxh, candidxw):
    if (idxh, idxw) not in se:
        print(ans)
        exit()
print(ans - 1)


Measured memory_bytes: 175260
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
  long long cnt=0;
  int n;
  cin >> n;
  vector<pair<int,int>> p(n);
  for(int i=0; i<n; i++) {
    cin >> p[i].second >> p[i].first;
  }
  sort(p.begin(),p.end());
  for(int i=0; i<n; i++) {
    cnt+=p[i].second;
    if(cnt>p[i].first) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#include<cstdio>
#define el "\n"
#define sp " "
typedef long long ll;

vector<string> ans(100005);
vector<string> s(100005);
ll n,y=0;
void dfs(ll i,ll a,ll b, ll c)
{
	if(y)
	return ;
	if(i==n)
	{
		cout<<"Yes"<<el;
		for(ll j=0;j<n;j++)
		cout<<ans[j]<<el;
		y=1;
	}
	if(s[i]=="AB")
	{
		if(b) ans[i]="A",dfs(i+1,a+1,b-1,c);
		if(a) ans[i]="B",dfs(i+1,a-1,b+1,c);
		
	}
		if(s[i]=="AC")
	{
		if(c) ans[i]="A",dfs(i+1,a+1,b,c-1);
		if(a) ans[i]="C",dfs(i+1,a-1,b,c+1);
	}
		if(s[i]=="BC")
	{
			if(c) ans[i]="B",dfs(i+1,a,b+1,c-1);
			if(b) ans[i]="C",dfs(i+1,a,b-1,c+1);
	}
	
}
main()
{
	ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll a,b,c;
cin>>n>>a>>b>>c;
for(ll i=1;i<=n;i++)
cin>>s[i-1];
dfs(0,a,b,c);
if(!y)
cout<<"No";

}

Measured memory_bytes: 20332
#include<iostream>

using namespace std;
int main()

{
int a,b,c,d;
cin>>a>>b>>c>>d;


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

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

else {
    cout<<a*b<<endl;
}


return 0;

}

Measured memory_bytes: 256
def check(s, p):
    for i in range(len(s)):
        count = 0
        for j in range(len(p)):
            if s[(i+j) % len(s)] != p[j]:
                break
            count += 1
        if count == len(p):
            return True
    return False

s = raw_input()
p = raw_input()
flag = check(s, p)
if flag:
    print("Yes")
else:
    print("No")

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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

template<typename T>
void print1(T begin, T end) {
  while (begin != end) {
    cout << (*begin) << " ";
    *begin++;
  }
  cout << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      cout << " " << Array[i][j];
    }
    cout << endl;
  }
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cerr << head << " ";
  print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1e9+7) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

// ------------------------------------------------------------------------------------------

int K, A, B;

signed main() {
  cin >> K >> A >> B;

  if (A >= B) {
    cout << K + 1 << endl;
    return 0;
  }
  int k = K;

  int ans = 1;
  // とりあえずA-1回叩く
  K -= (A - 1);
  ans += A - 1;

  ans += (B - A) * (K / 2);
  if (K % 2) ans++;

  cout << max(ans, k+1) << endl;

  return 0;
}

Measured memory_bytes: 256
class UnionFind:
	def __init__ (self, n):
		self.n = n
		self.parent = [i for i in range(n)]
		self.rank = [1] * n
		self.size = [1] * n

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			self.parent[x] = self.find(self.parent[x])
			return self.parent[x]
	
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.parent[x] = y
				self.size[y] += self.size[x]
			else:
				self.parent[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1
	
	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	def group_size(self, x):
		return self.size[self.find(x)]

N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M
C, D = [0] * K, [0] * K

direct = [[] for _ in range(N)]
uf = UnionFind(N)

for i in range(M):
	A[i], B[i] = map(int, input().split())
	A[i] -= 1
	B[i] -= 1
	direct[A[i]].append(B[i])
	direct[B[i]].append(A[i])
	uf.unite(A[i], B[i])

for i in range(K):
	C[i], D[i] = map(int, input().split())
	C[i] -= 1
	D[i] -= 1
	if uf.is_same(C[i], D[i]):
		direct[C[i]].append(D[i])
		direct[D[i]].append(C[i])

ans = [0] * N
for i in range(N):
	ans[i] = uf.group_size(i) - len(direct[i]) -1
print(*ans) 

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

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

int main() {
	int h, m, a, b;
	double hd, hm,rd;
	cin >> a >> b >> h >> m;
	hd = h * 30 + m * 0.5;
	hm = m * 6;
	if (hd == 0)hd = 360;
	if (hm == 0)hm = 360;
	if (hd < hm)rd = hm - hd;
	else rd = hd - hm;
	rd = rd * acos(-1) / 180;
	double ans = sqrt(a * a + b * b - 2 * a * b * cos(rd));
	cout << fixed << setprecision(12) << ans << endl;
	return 0;
}


Measured memory_bytes: 4172
data = list(map(int,input().split()))
N = data[0]
A = data[1]
B = data[2]
S = input()

passing = 0 

foreigner = 0 

for i in range(N):
    if S[i] == 'a':
        if passing < A+B:
            print("Yes")
            passing += 1
        else:
            print("No")

    elif S[i] == 'b':
        if passing < A+B and foreigner < B:
            print("Yes")
            passing += 1
            foreigner += 1
        else:
            print("No")

    else:
        print("No")

Measured memory_bytes: 4016
import sys
from collections import Counter
input = sys.stdin.readline

N, M = map(int, input().split())
uni, dup = [0]*M, [0]*M
for k, v in Counter(map(int, input().split())).items():
    uni[k % M] += v % 2
    dup[k % M] += v - (v & 1)

ans = (uni[0] + dup[0]) // 2

for i in range(1, (M+1)//2):
    x = min(uni[i], uni[M-i])
    y = min(uni[i]-x, dup[M-i])
    z = min(uni[M-i]-x, dup[i])
    ans += x + y + z + (dup[M-i]-y)//2 + (dup[i]-z)//2

if M % 2 == 0:
    ans += (uni[M//2] + dup[M//2]) // 2

print(ans)


Measured memory_bytes: 24236
s=list(str(input()))

Ans1=0
for index in range(len(s)):
    if s[index]=="A":
        Ans1=index
        break

Ans2=0
for index in reversed(range(0,len(s))):
    if s[index]=="Z":
        Ans2=index
        break
        
print(Ans2-Ans1+1)

Measured memory_bytes: 4840
n = gets.to_i
height = gets.split(' ').map &:to_i

res = 0
height.each_with_index do |m, i|
    if i == 0
        res += 1
        next
    end

    flag = true
    (0..(i - 1)).each do |j|
        if m < height[j]
            flag = false
            break
        end
    end

    res += 1 if flag
end

puts res

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

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

typedef pair<int, int> P;

const int N = 1e6+5;
string s,t;
vector<ll> v;
ll a,b,k;

int main () {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  cin >> a >> b >> k;
  if(a+b <= k) {
    cout << "0 0" << endl;
    return 0;
  }
  ll taka = a - k > 0 ? a-k : 0;
  ll aoki = a - k > 0 ? b : b+a-k;
  cout << taka << " " << aoki << endl;
}


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

int p_count;
vector<tuple<int, int, int>> pyramid;
vector<tuple<int, int, int>> measure;

void init_pyramid()
{
  p_count = 101 * 101;
  for (auto y = 0; y <= 100; y++) {
    for (auto x = 0; x <= 100; x++) {
      pyramid.emplace_back(make_tuple(x, y, 0));
    }
  }
}

void read_measure_data()
{
  int n;
  cin >> n;
  for (auto i = 0; i < n; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    measure.emplace_back(make_tuple(a, b, c));
  }
}

void check1()
{
  for (auto&& m : measure) {
    for (auto&& p : pyramid) {
      if (get<2>(p) < 0) continue;
      if (get<2>(m) == 0) continue;
      int guess = get<2>(m) + abs(get<0>(p) - get<0>(m)) + abs(get<1>(p) - get<1>(m));
      if (get<2>(p) == 0) {
	get<2>(p) = guess;
      } else if (get<2>(p) != guess) {
	get<2>(p) = -1;
	if (--p_count <= 1) return;
      }
    }
  }
}

void check2()
{
  for (auto&& m : measure) {
    for (auto&& p : pyramid) {
      if (get<2>(p) < 0) continue;
      if (get<2>(m) != 0) continue;
      int guess = abs(get<0>(p) - get<0>(m)) + abs(get<1>(p) - get<1>(m));
      if (guess - get<2>(p) < 0) {
	get<2>(p) = -1;
	if (--p_count <= 1) return;
      }
    }
  }
}

void print_ans()
{
  for (auto&& p : pyramid) {
    if (get<2>(p) > 0) {
      cout << get<0>(p) << " " << get<1>(p) << " " << get<2>(p) << endl;
    }
  }
}

int main()
{
  init_pyramid();
  read_measure_data();
  check1();
  check2();
  print_ans();
}


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

using namespace std;
#define  ll long long
#define ld long double
#define f first
#define s second

deque<char> q;
string s;
int qy , t , f;
char ch;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> s;
    for(int i=0; i<s.size(); i++)
    {
        q.push_back(s[i]);
    }

    int isRev=0; //0 if no , 1 if yes
    cin >> qy;
    while(qy--)
    {
        cin >> t;
        if (t==1) isRev ^= 1;
        else
        {
            cin >> f >> ch;
            if (f==1) //at begin
            {
                if (!isRev) q.push_front(ch);
                else q.push_back(ch);
            }
            else
            {
                if (!isRev) q.push_back(ch);
                else q.push_front(ch);
            }
        }
    }

    if (isRev)
    {
        while(q.size()) cout << q.back() , q.pop_back();
    }
    else
    {
        while(q.size()) cout << q.front() , q.pop_front();
    }
    return 0;
}

Measured memory_bytes: 976
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
template<class Read>void in(Read &x){
    x=0;
    int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        f|=(ch=='-');
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x=f?-x:x;
    return;
}
int n,s,e,ans,head[100005],top,g[100005],f[100005],fa[100005];
struct Node{
    int nxt;
    int to;
}a[200005];
void add(int x,int y){
    a[++top].nxt=head[x];
    a[top].to=y;
    head[x]=top;
}
void dfs(int x,int fat){
    f[x]=g[x]=f[fat]+1;
    fa[x]=fat;
    for(int i=head[x];i;i=a[i].nxt){
        int y=a[i].to;
        if(y==fat)continue;
        dfs(y,x);
        g[x]=max(g[x],g[y]);
    }
}
int main(){
    in(n);in(s);in(e);
    for(int i=1;i<n;i++){
        int x,y;
        in(x);in(y);
        add(x,y);
        add(y,x);
    }
    dfs(e,0);
    int now=s;
    while(f[s]-f[now]<f[now]-f[e]){
        ans=max(ans,g[now]-1);
        now=fa[now];
    }
    printf("%d\n",ans-1);
    return 0;
}


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

const int N = 1e5 + 5;
int a[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

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

    int mx = *max_element(a, a + n), dist = 1e9, x;

    for (int i = 0; i < n; i++) {
        if (a[i] == mx)
            continue;
        
        int cur_dist;
        if (mx % 2) {
            if (a[i] <= mx / 2)
                cur_dist = mx / 2 - a[i];
            else
                cur_dist = a[i] - mx / 2 - 1;
        }
        else {
            cur_dist = abs(a[i] - mx / 2);
        }

        if (cur_dist < dist) {
            dist = cur_dist;
            x = a[i];
        }
    }

    cout << mx << " " << x;

    return 0;
}

Measured memory_bytes: 640
A = gets.to_i
B = gets.to_i
C = gets.to_i
X = gets.to_i

ans = 0
(0..A).each do |c500|
  (0..B).each do |c100|
    (0..C).each do |c50|
      ans += 1 if 500 * c500 + 100 * c100 + 50 * c50 == X
    end
  end
end
puts ans


Measured memory_bytes: 1788
import numpy as np
import math
from decimal import Decimal

def resolve():
  S = input().split(" ")
  # print(math.floor(int(S[0])*Decimal(S[1])))
  print(math.floor((int(S[0]) * int(float(S[1])*1000))) // 1000)

  

if __name__ == "__main__":
  resolve()

Measured memory_bytes: 27020
#include <stdio.h>

int main(void)
{
	int a, b, c, isok = 0;
	scanf("%d%d", &a, &b);
	for (c = 1; c <= 3; ++c)
		if ((a * b * c) % 2 == 1)
			isok = 1;
	if (isok) puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const double PI  = acos(-1.0);
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define print(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 
int main()
{
    int A[5];
    rep(i, 5){
        cin >> A[i];
        if (A[i] == 0){
            cout << (i + 1) << endl;
            return 0;
        }
    }
    return 0;
}



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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) (((a)+(b)-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2
#define PI acos(-1.0)
#define SUM(v) accumulate((v).begin(),(v).end(),0ll)
#define range(i,left,right) (left<=i && i<right)

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;
typedef priority_queue<int> PQi;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vout(Vs &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vvout(VVi &v){for(int i=0;i<(v).size();i++) vout(v[i]);}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int mypow(int x, int n, int m){if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}
int digit(int k,int i){string s = to_string(k);return s[s.size()-i]-'0';}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());} //vectorの同じ要素消す
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
int leng(int n){string s=to_string(n); return s.size();} //intの桁数
int digitsum(int n){int ret=0; while(n>0){ret+=n%10;n/=10;}return ret;} //桁和
int lesscount(int x,Vi &a){return lower_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx未満の数の個数
int orlesscount(int x,Vi &a){return upper_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx以下の数の個数
int morecount(int x,Vi &a){return a.size()-orlesscount(x,a);} //vector aにおけるxより大きい数の個数
int ormorecount(int x,Vi &a){return a.size()-lesscount(x,a);} //vector aにおけるx以上の数の個数
int iscount(int x,Vi &a) {return upper_bound(ALL(a),x)-lower_bound(ALL(a),x);} //vector aにおけるxの個数
Vi accum(Vi &v){Vi ret((v).size()+1);REP(i,0,(v).size()) ret[i+1]=ret[i]+v[i];return ret;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);
    int n,k;
    cin>>n>>k;
    Vi a(n);
    REP(i,0,n){
        cin>>a[i];
        a[i]--;
    }

    Vi loop;
    set<int> se;
    loop.pb(0);
    se.insert(0);

    int d;
    while(1){
        if(se.count(a[loop[loop.size()-1]])){
            d=a[loop[loop.size()-1]];
            break;
        }
        se.insert(a[loop[loop.size()-1]]);
        loop.pb(a[loop[loop.size()-1]]);
    }

    int before=0,loopnum=0;
    bool check=false;
    REP(i,0,loop.size()){
        if(loop[i]==d) check=true;
        if(check) loopnum++;
        else before++;
    }
    if(k<loop.size()) cout<<loop[k]+1<<endl;
    else{
        cout<<loop[(k-before)%loopnum+before]+1<<endl;
    }
}

Measured memory_bytes: 15352
#include <iostream>
#include <cstdio>
using namespace std;
int n,a[100001],odd,sum;
int gcd(int x,int y){
	if (!y) return x;
	return gcd(y,x%y);
}
int f(){
	int o=0,e=0,i,g;
	for (i=1;i<=n;++i)
		if (a[i]&1){
			++o;
			odd=i;
		}else ++e;
	if (o==1&&a[odd]!=1){
		--a[odd];
		g=a[1];
		for (i=2;i<=n;++i) g=gcd(g,a[i]);
		for (i=1;i<=n;++i) a[i]/=g;
		return 1-f();
	}else{
		for (i=1;i<=n;++i) sum+=a[i];
		if ((sum+n)&1) return 1;
		else return 0;;
	}
}
void read(int& x){
    x=0;
    int y=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') y=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    x=x*y;
}
int main(){
	int i;
	read(n);
	for (i=1;i<=n;++i) read(a[i]);
	if (f()) printf("First\n");
	else printf("Second\n");
	return 0;
}

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

// Union-Find 木 (Verified: AtCoder Typical Contest 001 B)
struct UnionFind {
 private:
  const int n;
  int size_;
  vector<int> uf;

 public:
  // 初期化 UnionFind uni(n) のように宣言すれば良い
  UnionFind(int _n) : n(_n), size_(_n), uf(_n, -1) {}
  // find (木の根を求める)
  int find(int x) { return (uf[x] < 0) ? x : uf[x] = find(uf[x]); }
  // x と y が同じ集合に属するかどうか
  bool same(int x, int y) { return find(x) == find(y); }
  // x が属する集合の要素数
  int size(int x) { return -uf[find(x)]; }
  // 集合はいくつあるか
  int size() { return size_; }
  // x と y の属する集合を併合
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    size_--;
    if (-uf[x] < -uf[y]) swap(x, y);
    uf[x] += uf[y];
    uf[y] = x;
    return true;
  }
};

int main() {
  int N, M, K;
  cin >> N >> M >> K;
  UnionFind uf(N);
  vector<int> ans(N);
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    uf.unite(u, v);
    ans[u]--;
    ans[v]--;
  }

  vector<vector<int> > G(N);
  for (int i = 0; i < K; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  for (int i = 0; i < N; i++) {
    ans[i] += uf.size(i) - 1;
    for (auto j : G[i]) {
      if (uf.same(i, j)) ans[i]--;
    }
    if (i) cout << " ";
    cout << ans[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 8996
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(all(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define PII         pair<int, int>
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

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...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int h, w;
    cin >> h >> w;
    char g[h + 2][w + 2];
    memset(g, '#', sizeof(g));
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> g[i][j];
        }
    }
    for(int i = 0; i <= h + 1; i++){
        for(int j = 0; j <= w + 1; j++){
            cout << g[i][j];
        }
        cout << nl;
    }
    return 0;
}


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

using namespace std; 
#define REP(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;
int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    string S; cin >> S;
    ll val = 0;
    ll res = 0;
    ll x = 0;
    while(x < (int)S.size()){
        while(S[x] == '<' && x <(int) S.size()) {
            val++;
            res += val;
            x++;
        }
        if (x == (int)S.size()) break;
        // cout << "after greater:" << res << endl;
        ll down = 0;
        ll pre_top = val;
        while (S[x] == '>' && x <(int) S.size()){
            val--;
            res += val;
            x++;
            down++;
        }
        // cout << "before lower:" << res << endl;
        if (val < 0) res -= (down+1) * val;
        else res -= down * val;
        // cout << "after lower:" << res << endl;
        val = 0;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 1172
def gcd(n,m):#n,mは正の整数、最大公約数　許容は？
    if n==0:
        return m
    elif m==0:
        return n
    elif n>m:
        n=n%m
        return gcd(n,m)
    else:
        m=m%n
        return gcd(n,m)

N,M=map(int,input().split())
A=list(map(int,input().split()))
realA=[A[i]//2 for i in range(0,N)]
lcm=realA[0]
flag=0
if N==1:
    print((M//lcm+1)//2)
else:
    for i in range(0,N-1):
        x=lcm
        lcm=lcm*realA[i+1]//(gcd(lcm,realA[i+1]))
        if (lcm**2//(realA[i+1]*x))%2==0:
            flag=1
            break
    if flag==0:
        print((M//lcm+1)//2)
    else:
        print(0)


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

using namespace std;

// typedef
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;

// container util
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

// repetition
#define FOR(i,m,n) for(ll (i) = ((ll) m); (i) < ((ll) n); ++(i))
#define RFOR(i,m,n) for(ll (i) = ((ll) (m)-1); (i) >= ((ll) n); --(i))
#define REP(i,n) FOR(i,0,n)

// i/o
#define TFOUT(b,t,f) cout << ((b)? (t) : (f)) << endl

//constant
const double    EPS     = 1e-10;
const double    PI      = acos(-1.0);
const int       INFTY   = (1<<21);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

double dist(vector<int> x, vector<int> y, int d) {
    double s = 0.0;
    for (int i = 0;  i < d; i++) {
        s += (x[i] - y[i])*(x[i] - y[i]);
    }
    return sqrt(s);
}

int main(void){
    int n, d;
    cin >> n >> d;
    vector< vector<int> > x;
    for(int i = 0; i < n; i++) {
        vector<int> t;
        for(int j = 0; j < d; j++) {
            int e; cin >> e;
            t.push_back(e);
        }
        x.push_back(t);
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            double dis = dist(x[i], x[j], d);
            double e = dis - (long long)dis;
            if (1e-6 > e && -1e-6 < e) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n,d=map(int,input().split())
x=[list(map(int,input().split()))for _ in range(n)]
ans=0
for i in range(n-1):
    for j in range(1,n-i):
        l=0
        for k in range(d):
            l+=(x[i][k]-x[i+j][k])**2
        l=l**0.5
        if l.is_integer()==True:
            ans+=1
print(ans)

Measured memory_bytes: 3064
import math

def prime(x):
    if x==1:
        prime=False
    else:
        prime=True
        for i in range(2,int(math.sqrt(x)+1)):
            if x%i==0:
                prime=False
                break
    return prime

def count_prime(N):
    p=[0 for n in range(int(math.sqrt(N)+1))]
    
    if prime(N):#初期値が素数の場合
        big_prime=True
        
    else:#初期値が素数でない場合
        big_prime=False
        rtN_init=int(math.sqrt(N)+1)
        
        #素因数分解。ルートＮまでの範囲で素因数を探す。見つかったらpの素因数インデックスを++
        while N>1:
            #素数がルートNを超える場合
            if prime(N) and N>rtN_init:
                big_prime=True
                break
            else:
                for i in range(2,rtN_init):
                    if N%i==0 and prime(i):
                        p[i]+=1
                        N=N//i
                        break
    return p,big_prime

def main():
    N=int(input())
    p,q=count_prime(N)
    cnt=0
    
    for n in range(len(p)):
        num=1
        while p[n]>=1:
            p[n]-=num
            if p[n]>=0:
                cnt+=1
                num+=1
    if q==True:
        cnt+=1
    print(cnt)
        
if __name__=="__main__":
    main()

Measured memory_bytes: 17020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1000000007;
int main(){
  ll n;cin >> n;
  vector<ll> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
    a[i]++;
  }
  vector<ll> c(n+1);
  c[0]=3;
  ll ans=1;
  for(int i=0;i<n;i++){
    ans*=c[a[i]-1]-c[a[i]];
    c[a[i]]++;
    ans%=mod;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792