akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	int n;
	cin >> n;

	vector<ll> a(n);
	map<ll, ll> mp;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		mp[a[i]]++;
	}

	deque<ll> deq;
	ll maxSecondPower = 0;
	for (auto m : mp) {
		if (m.second < 2) {
			continue;
		} else if (m.second >= 4) {
			maxSecondPower = m.first * m.first;
		}

		deq.push_back(m.first);
		if (deq.size() > 2) {
			deq.pop_front();
		}
	}

	if (deq.size() >= 2) {
		ll a = deq.front(); deq.pop_front();
		ll b = deq.front(); deq.pop_front();
		cout << (max(a * b, maxSecondPower)) << endl;
	} else if (maxSecondPower != 0) {
		cout << maxSecondPower << endl;
	} else {
		cout << 0 << endl;
	}
	return 0;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1e18;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;



int main() {
  int n;
  scanf("%d",&n);
  vi a(n);
  cin>>a;
  cout<<suma(a)-n<<endl;
  return 0;
}






















Measured memory_bytes: 256
import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        new Main().compute();
    }

    void compute() {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            System.out.println((int) Math.log10(sc.nextInt() + sc.nextInt()) + 1);
        }
    }
}


Measured memory_bytes: 26448
import java.awt.Rectangle;
import java.util.Scanner;


public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int w = sc.nextInt();
            int h = sc.nextInt();
            
            int n = sc.nextInt();
            int num = 0;
            for (int j = 0; j < n; j++) {
                int xj = sc.nextInt();
                int yj = sc.nextInt();
                if (x <= xj && xj <= x + w && y <= yj && yj <= y + h) {
                    num++;
                }
            }
            System.out.println(num);
        }
    }

}

Measured memory_bytes: 0
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_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())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define CLR(a) memset((a), 0 ,sizeof(a))

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

int main(void){
  int x;
  cin >> x;
  cout << x*x*x << endl;
  return 0;
}

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

using namespace std;



int main() {
	
  int N,count;cin >> N;
  count = 0;
  string s;
  for(int i=1;i<=N;i++){
    s = to_string(i);
    int leng = s.length();
    
    if(leng%2==1) count++;
  }
  cout << count;
}




Measured memory_bytes: 256
#include <stdio.h>

int main( void ){
	int i, j, n, m, minj, count;  //mは交換に使う変数
	scanf("%d", &n);
	int A[n];
	for(i = 0; i < n; i++){
        scanf("%d", &A[i]);
    }
	
	count = 0;
	for(i = 0; i < n; i++){
		minj = i;
		for(j = i; j < n; j++){
			if(A[j] < A[minj]){
				minj = j;
			}
		}
		if(i != minj){
			count++;
		}
		m = A[i];
		A[i] = A[minj];
		A[minj] = m;		
	}
	
	for(i = 0; i < n; i++){
        printf("%d", A[i]);
        if(i < n - 1){
            printf(" ");
        }
    }
    printf("\n");
    printf("%d\n", count);
	
	return 0;
}



Measured memory_bytes: 2032
# 1からNまでの数字それぞれの約数を求める
# Nから(大きい値から)見ていき、1であれば入れる
# 数字iを入れた場合、iの約数の数を+1
# それぞれの数はdictで保持する

N = int(input())
A = list(map(int, input().split()))

ans = [0 for _ in range(N)]

ans_num = 0
ans_list = ""
for i in range(N):
    tmp = N - i
    s = 0
    for j in range(tmp, N+1, tmp):
        s += ans[j-1]

    if s % 2 != A[tmp - 1]:
        ans[tmp - 1] = 1
        ans_num += 1
        ans_list += str(tmp)
        ans_list += " "


print(ans_num)
print(ans_list[:-1])

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

int main(){
 	int  N,sum(0);
  	cin >> N;
  	vector<int> L(N);
  	for(int i = 0 ; i < N ; i ++){
     	cin >> L[i];
      	sum += L[i];
    }
  	sort(L.begin(),L.end());
  	if(sum - L[N - 1] > L[N - 1]) cout << "Yes" << endl; else cout << "No" << endl;
}

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

int N;
int A[100005];

int solve() {
  
  if (N == 2) return A[0] >= A[1] ? A[0] : A[1];
  
  sort(A, A + N);
    
  for (int v = A[1]; v >= 1; v--) {
    int sum = 0;
    
    for (int i = 0; i < N; i++) {
      if ( A[i] % v != 0 ) sum++;
      
      if (sum >= 2) break;
    
    }
    
    if (sum <= 1) return v;
    
  }
    


}

int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  
  int ans = solve();
  
  printf("%d\n", ans);
  
  

}

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

#define ONLINE_JUDGE
#define ll long long
#define PI 3.14159265359
#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
#define pb(a) push_back(a)

//////////// Solution /////////////////////////////////

void solve() {
	int a,b,t;
	cin >> a >> b >> t;
	int k = t/a;
	cout << b*k << '\n';
}


/////////// End Solution ///////////////////////////////////////

//////// Initialization ////////////////////////////////////

int main() {

	#ifndef ONLINE_JUDGE
	FILE *FIN = freopen("/home/danil/prog/input.txt", "r", stdin);
	clock_t time_start = clock();
	#endif

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

	solve();

	#ifndef ONLINE_JUDGE
	fclose(FIN);
	cerr << "\x1b[031m\n-----------------\nTime=" << (ll)((double)(clock()-time_start) / CLOCKS_PER_SEC * 1000) << "ms\n\x1b[0m";
	#endif

	return 0;
}

//////// End Initialization ///////////////////////////////////////

Measured memory_bytes: 384
from math import ceil

N = int(input())
As = list(map(int, input().split()))

# dpの右から(j+1)ビット目: 和がjである部分列が存在するならば1
dp = 1
for A in As:
    dp |= dp << A

# 和がjである部分列が存在する、(ΣA/2)以上で最小のjが答え
ans = ceil(sum(As) / 2)
dp >>= ans
while not (dp & 1):
    dp >>= 1
    ans += 1

print(ans)


Measured memory_bytes: 5464
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int a=scan.nextInt();
		int b=scan.nextInt();
		int count=1;
		for(int i=0;i!=a;i++) {
			count*=100;
		}
		if(b==100) {
			b++;
		}
		System.out.println(count*b);
	}
}

Measured memory_bytes: 21844
import sys
input = sys.stdin.readline

def linput():
    return [int(x) for x in input().split()]

mod = 10**9 + 7

n, k = linput()

cnt = [0] * (k + 1)

for i in range(1, k + 1):
    cnt[i] = k // i

for i in range(1, k + 1):
    cnt[i] = pow(cnt[i], n, mod)

ans = 0
#約数の列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


for i in range(k, 0, -1):
    ans += cnt[i] * i
    ans %= mod
    d = make_divisors(i)
    for j in d:
        cnt[j] -= cnt[i]

print(ans)

Measured memory_bytes: 69892
def solve():
    x, k, d = map(int, input().split())
    x = abs(x)
    ref, a = divmod(x, d)
    if k < ref:
        print(x - k * d)
    elif ref % 2 == k % 2:
        print(a)
    else:
        print(d - a)

solve()


Measured memory_bytes: 9168
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		ArrayList<Integer> one = nextIntArray();
		int H = one.get(0);
		int A = one.get(1);
		myout((H + A - 1) / A);
	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 33016
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
#include <array>
#include <map>
#include <string>
using namespace std;
#define ll long long;

int main(void)
{
  string s;
  cin >> s;
  int size=s.size();
  if((size % 2==0) ^ (s[0]==s[size-1]))
    {
      cout << "Second" << endl;
      return 0;
    }
    else
      {
	cout << "First" << endl;
	return 0;
      }
}


Measured memory_bytes: 512
#include<stdio.h>

int N,a,j;
int hoge[1000]={0};
int huga[1000]={0};

int  main(void){
	scanf("%d ",&N);
for(int i=1;i<=N;i++){
		scanf("%d",&hoge[i-1]);
	}

for(int i=0;i<N;i++){
		
			for( j=0;j<N;j++){
				if(i>=j){
					;
					}else{
				a+=hoge[i]*hoge[j];
				}
			}
		
		
		
	}	

	printf("%d",a);
}
		

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		int[]A = new int[4];
		for(var i=0;i<4;i++){
			A[i] = int.Parse(str[i]);
		}
		Array.Sort(A);
		if(A[0]==1&&A[1]==4&A[2]==7&A[3]==9){
			Console.WriteLine("YES");
		} else {
			Console.WriteLine("NO");
		}
	}
}

Measured memory_bytes: 11092
# Author: cr4zjh0bp
# Created: Tue Mar 24 00:01:43 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

a,b,c=nas()
print(str.upper(a[0])+str.upper(b[0])+str.upper(c[0]))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define nl '\n'
#define f(i, n) for (int i = 0; i < n; ++i)

using namespace std;
void solve() {
    ll n, x, t;
    cin >> n >> x >> t;
    ll ans = (n % x) ? n / x + 1 : n / x;
    cout << ans * t << nl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m1(x) memset(x,-1,sizeof(x))
const int INF = 1e9 + 1;
const ll MOD = 1e9 + 7;
const double PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799;


int main(){
  int n, k;
  cin >> n >> k;
  int ans = 0;
  int h[100000];
  rep(i, n) cin >> h[i];
  rep(i, n){
    if(h[i] >= k) ans++;
  }
  cout << ans <<endl;
  
}

Measured memory_bytes: 640
"""
N = 2, 3, 4,...と実験していくと何となく再帰的な構造が見える。
ここで文字列の末尾に再帰構造を見出そうとするときれいにいかず失敗する。
（例）
    N = 3                   N = 4
    a---a---a               a---a---a---a
    '   '---b               '   '   '---b
    '---b---a               '   '---b---a
        '---b               '       '---b
        '---c               '       '---c
                            '---b---a---a
                                '   '---b
                                '   '---c
                                '---b---a
                                '   '---b
                                '   '---c
                                '---c---a
                                    '---b
                                    '---c
                                    '---d

正しくは先頭から再帰構造を見出すべき（数学的帰納法を先頭にかけるのと似た感じ。。。）
するとN=4の場合の樹形図の左から３列目まではN=3と全く同じ形なことに気づく。

よって左から木を生やしていき、（根から葉まで使われた文字数）＋１が新しい葉として生じる。

ここで実際に木を構成するのは面倒そうなので、実装時にはNの各値に対して
（根から葉までの文字列＋使われた最後位の文字）の組をリストに格納する。
（例）N=4なら
    [("aaaa", "a"), ("aaab", "b"), ("aaba", "b"), ("aabb", "b"), ("aabc", "c"), ("abaa", "b"),...]
各組をpopleftすれば、それから新しい文字列（新しい葉）が構成可能。
"""

from collections import deque

N = int(input())
leaf = deque([("a", "a")])
newleaf = []
for _ in range(N - 1):
    while leaf:
        string, maxchar = leaf.popleft()
        maxnum = ord(maxchar) # maxcharをASCIIコードに変換
        for i in range(97, maxnum + 2):
            newleaf.append((string + chr(i), chr(max(maxnum, i))))
    leaf = deque(newleaf)
    newleaf = []

for s in leaf:
    print(s[0])



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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int h, w;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    cin >> h >> w;
    vector<string> s(h);
    rep (i, h) cin >> s[i];
    vector<vector<bool> > visited(h, vector<bool>(w, false));
    ll res = 0;
    rep (i, h) {
        rep (j, w) {
            if (visited[i][j]) continue;
            queue<pair<int, int> > q;
            q.push(make_pair(i, j));
            ll black = 0, white = 0;
            visited[i][j] = true;
            while (!q.empty()) {
                int x, y;
                x = q.front().first, y = q.front().second;
                q.pop();
                if (s[x][y] == '#') black++;
                else white++;
                rep (k, 4) {
                    int nx, ny;
                    nx = x + dx[k], ny = y + dy[k];
                    if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                    if (visited[nx][ny]) continue;
                    if (s[x][y] == s[nx][ny]) continue;
                    visited[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                }
            }
            res += black * white;
        }
    }
    cout << res << endl;
    
    return 0;
}



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

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

    vector<int> values(n);
    vector<int> costs(n);
    for (size_t i = 0; i < n; i++)
    {
        cin >> values[i];
    }
    for (size_t i = 0; i < n; i++)
    {
        cin >> costs[i];
    }

    int max = 0;
    for (size_t i = 0; i < n; i++)
    {
        if (values[i] > costs[i])
        {
            max += values[i] - costs[i];
        }
    }

    cout << max << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a;
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputDoubleArray(a,N) double a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
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; }


int main(){
  inputInt3(A,B,C);
  
  if(C-1 > A+B){//毒入りの方が多い→解毒剤入りの枚数+1
    output(A+B+1 + B); 
  }else{
    output(B+C); 
  }
  
  return 0;
}


Measured memory_bytes: 256
import copy

INF = 10000000000
def merge(A, left, mid, right):
    count = 0
    L = A[left:mid] + [(INF,INF)]
    R = A[mid:right] + [(INF,INF)]
    
    i, j = 0, 0
    for k in range(left, right):
        count = count + 1
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
    return count

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        countL = mergeSort(A, left, mid)
        countR = mergeSort(A, mid, right)
        return merge(A, left, mid, right) + countL + countR
    return 0



def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]

    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

def quickSort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q+1, r)
        
    
n = int(input())
A = [None for i in range(n)]
for i in range(n):
    a, b = input().split()
    A[i] = (a, int(b))

B = copy.deepcopy(A)
quickSort(A, 0, n-1)
mergeSort(B, 0, n)
if A == B:
    print("Stable")
else:
    print("Not stable")

ans = [str(x[0]) +" "+str(x[1]) for x in A]
ans = '\n'.join(ans)
print(ans)



Measured memory_bytes: 24624
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define SZ(X) ((int64_t)((X).size()))
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define intmax (std::numeric_limits<int64_t>::max() / 4)
#define doublemax (std::numeric_limits<double>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);



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

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

	sort(ALL(A));

	vector<int>acc(N);
	acc[0] = A[0];
	REP(i, 1, N)acc[i] = acc[i - 1] + A[i];

	int ans = 1;
	for (int i = N - 1; 1 <= i; i--) {
		if (acc[i - 1] * 2 < A[i])break;
		ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define int long long
int INF = 1e9+7;
int dp[200005];
signed main() {
    int N;
    cin >> N;
    vector<int>cnt(200005,-1);
    vector<int>C(N);
    dp[0] = 1;
    for(int i = 0; i < N; i++) {
        cin >> C[i];
        dp[i+1] += dp[i];
        if(i) {
            if(C[i] == C[i-1]) {
                goto END;
            }
        }
        if(cnt[C[i]] != -1) {
            dp[i+1] += dp[cnt[C[i]]+1];
        }
        dp[i+1] %= INF;
        END:;
        cnt[C[i]] = i;
    }
    cout << dp[N] << endl;
}

Measured memory_bytes: 8064
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>

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

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    cout << n / ( a + b ) * a + min(a, n % ( a + b )) << endl;
    return 0;
}


Measured memory_bytes: 256
my @num = map { $_ - 0 } split //, <STDIN>;
my $ops = ['+', '-', '*', '/'];
my $his = [0, 0, 0, 0];
sub op {
    my ($n, $opn, $r) = @_;
    $r += $num[$n] if $opn == 0;
    $r -= $num[$n] if $opn == 1;
    $r *= $num[$n] if $opn == 2;
    if($opn == 3) {
        return if $num[$n] == 0;
        $r /= $num[$n];
    }
    $his->[$n] = $opn;
    if($n == 3) {
        if($r == 7) {
            for(my $p = 0; $p < 4; $p++) {
                print $num[$p];
                print $ops->[$his->[$p + 1]] if $p != 3;
            }
            print '=7';
            exit;
        }
        return;
    }
    for(my $op2 = 0; $op2 < 4; $op2++) {
        op($n + 1, $op2, $r);
    }
}
op(0, 0, 0);

Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n, k; cin >> n >> k;
  vector<int> a(n); REP(i, n) cin >> a[i];
  vector<bool> dp(k+1, false);
  FOR(i, 1, k+1) {
    REP(j, n) if (i - a[j] >= 0 && !dp[i-a[j]]) {
      dp[i] = true;
      break;
    }
  }
  cout << (dp[k]? "First" : "Second") << '\n';
  return 0;
}


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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define fth(t) std::get<3>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;


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

int V, E, F;
// to, rev, cap, cost
std::vector<std::tuple<int, int, int, int>> G[200];

void addEdge(int u, int v, int cap, int cost){
    G[u].emplace_back(v, G[v].size(), cap, cost);
    G[v].emplace_back(u, G[u].size() - 1, 0, -cost);
}

int dist[1500];
tuple<int, int, int> prevs[1500];
const int INF = numeric_limits<int>::max() / 2;

void bellmanFord(int s){
    std::fill(dist, dist+V, INF);
    std::fill(prevs, prevs+V, std::make_tuple(-1, -1, -1));
    dist[s] = 0;

    for(int i=0;i<V;++i){
        bool updated = false;
        
        for(int u=0;u<V;++u){
            for(int k=0;k<G[u].size();++k){
                const auto& p = G[u][k];
                int v, rev, cap, c;
                std::tie(v, rev, cap, c) = p;
                if(cap <= 0){continue;}
                if(dist[v] > dist[u] + c){
                    updated = true;
                    dist[v] = dist[u] + c;
                    prevs[v] = std::make_tuple(u, k, rev);
                }
            }            
        }

        if(!updated){break;}
    }
}

int f(){
    ll res = 0;
    
    while(F > 0){
        bellmanFord(0);

        if(dist[V-1] == INF){
            return -1;
        }
        
        int v = V - 1;
        int d = F;
        while(v != 0){
            int pv, e_idx;
            tie(pv, e_idx, ignore) = prevs[v];

            d = min(d, thd(G[pv][e_idx]));
            
            v = pv;
        }

        F -= d;
        res += 1ll * d * dist[V-1];

        v = V - 1;
        while(v != 0){
            int pv, e_idx, rev;
            tie(pv, e_idx, rev) = prevs[v];

            thd(G[pv][e_idx]) -= d;
            thd(G[v][rev]) += d;
            
            v = pv;
        }        
    }

    return res;
}

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

    std::cin >> V >> E >> F;

    for(int i=0;i<E;++i){
        int u, v, c, d;
        std::cin >> u >> v >> c >> d;

        addEdge(u, v, c, d);
    }

    ll res = f();
    std::cout << res << std::endl;
}

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

int main(){
    long long w, h;
    long long x, y;
    cin >> w >> h >> x >> y;

    int isOK = 0;
    if(w % 2 == 0 && w/2 == x && h % 2 == 0 && h/2 == y){
        isOK = 1;
    }


    printf("%.12lf %d\n", (double)(w*h / 2.0), isOK);

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;

ll solve(int N) {

  static ll dp[2][1<<16]; zero(dp);
  ll res = 0;

  rep(i, N) {
    int M; ll L; scanf("%d%lld",&M,&L);

    int bit = 0;
    rep(_, M) {
      int s, t; cin >> s >> t; s -= 6, t -= 6;
      bit |= ((1<<t)-1) - ((1<<s)-1);
    }

    rep(S, 1<<16) {
      maximize(dp[(i+1)&1][S], dp[i&1][S]);
      if((S ^ bit) == (S + bit)) {
        int nS = S ^ bit;
        maximize(dp[(i+1)&1][nS], dp[i&1][S] + L);
        maximize(res, dp[(i+1)&1][nS]);
      }
    }
  }
  return res;
}

int main() {

  for(int N; ~scanf("%d", &N) && N;) {
    printf("%lld\n", solve(N));
  }
  
  return 0;
}

Measured memory_bytes: 4236
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);

		int n=sc.nextInt();		//n個の偶数
		int m=sc.nextInt();		//m個の奇数
		
		System.out.println(n*(n-1)/2+m*(m-1)/2);
	}

}


Measured memory_bytes: 21844
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n;
int x;
int sum;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(x%2==0)
			sum++;
	}
	if(sum==n)
		cout<<"second";
	else
		cout<<"first";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define fi first
#define se second
#define pi 3.141592653589793
#define mod 1e9 + 7
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.begin(), v.end(), greater<ll>()
#define tc int t;cin>>t;while(t--)
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vi,greater<int>>
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
#define tc_g int tt;cin>>tt;for(int ti=1;ti<=tt;ti++)
#define case_g "Case #"<<ti<<": "
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;
using namespace std;
int main() {
    string arr[] = {"SAN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    string ss;
    cin >> ss;
    int ans = 0;
    for(int i = 0; i < 7; ++i) {
        if(ss == arr[i]) {
            ans = i;
            break;
        }
    }
    if(ans > 0) {
        ans = 6 - ans  + 1;
    }
    else
        ans = 7;
    cout << ans;
}


Measured memory_bytes: 256
#include<cstdio>
#include<map>
using namespace std;
typedef long long ll;
int i,j,k,n,m,ff,ch,pn,ans,Fg;
ll s;
int p[3030];
map<ll,ll> S;
map<ll,int> Map;
map<ll,int>::iterator it;
void R(ll &x) {
	ff=x=0;ch=getchar();
	while (ch<'0' || '9'<ch) { if (ch=='-') ff=1;ch=getchar();}
	while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
	if (ff) x=-x;
}
bool check(int x) {
	for (int i=2;i*i<=x;i++) if (x%i==0) return 0;
	return 1;
}
ll sqrt(ll x) {
	ll l=1,r=100000,mid;
	while (l<r) {
		mid=(l+r+1)>>1;
		if (mid*mid<=x) l=mid;
		else r=mid-1;
	}
	return l;
}
int main() {
	scanf("%d",&n);
	for (i=2;i<=3000;i++) if (check(i)) p[++pn]=i;
	for (i=1;i<=n;i++) {
		R(s);
		ll a=1,b=1;
		for (j=1;j<=pn;j++) if (s%p[j]==0) {
			ll t=0;
			while (s%p[j]==0) s/=p[j],t++;
			t%=3;
			if (!t) continue;
			for (k=0;k<t;k++) a*=p[j];
			for (k=3;k>t;k--) b*=p[j];
		}
		ll t=sqrt(s);
		if (t*t==s) a*=s,b*=t;
		else {
			if (10000000000ll/b/s/s>=1) a*=s,b*=s*s;
			else {
				ans++;
				continue;
			}
		}
		if (a==1) Fg=1;
		else {
			S[a]=b;
			Map[a]++;
		}
	}
	ans+=Fg;
	for (it=Map.begin();it!=Map.end();it++) {
		ll a=(*it).first;
		ll b=S[a];
		if (Map[a]<Map[b] || (Map[a]==Map[b] && a<b)) continue;
		ans+=Map[a];
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 20864
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

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

int n, m;
int sti, stj, fii, fij;
string s[maxn];

int d[maxn * maxn];
bool vis[maxn * maxn];

void read_input()
{
    cin >> n >> m;
    cin >> sti >> stj;
    cin >> fii >> fij;
    --sti; --stj; --fii; --fij;
    for(int i = 0; i < n; ++i)
        cin >> s[i];
}

int modify(int i, int j)
{
    return i * m + j;
}

void solve()
{
    fill(begin(d), end(d), -1);
    fill(begin(vis), end(vis), false);
    deque<int> dq;
    d[modify(sti, stj)] = 0;
    dq.push_back(modify(sti, stj));
    while(!dq.empty())
    {
        int u = dq.front(); dq.pop_front();
        if(vis[u]) continue;
        vis[u] = true;
        int i = u / m, j = u % m;
        for(int k = 0; k < 4; ++k)
        {
            int ii = i + dx[k], jj = j + dy[k];
            if(ii < 0 || ii >= n || jj < 0 || jj >= m || s[ii][jj] == '#') continue;
            int v = modify(ii, jj);
            if(d[v] == -1 || d[v] > d[u])
            {
                d[v] = d[u];
                dq.push_front(v);
            }
        }
        for(int ii = max(0, i - 2); ii < min(i + 3, n); ++ii)
            for(int jj = max(0, j - 2); jj < min(j + 3, m); ++jj)
            {
                if(s[ii][jj] == '#') continue;
                int v = modify(ii, jj);
                if(d[v] == -1 || d[v] > d[u] + 1)
                {
                    d[v] = d[u] + 1;
                    dq.push_back(v);
                }
            }
    }
    cout << d[modify(fii, fij)] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}



Measured memory_bytes: 9592
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

void dfs(vector< vector<int> > &G,
         vector<ll> &mark, vector<ll> &ans,
         ll sum, int cur, int par=-1) {
    sum += mark[cur];
    ans[cur] = sum;

    for(auto to : G[cur]) {
        if(to == par) continue;
        dfs(G, mark, ans, sum, to, cur);
    }
}
 
int main() {
    int N, Q; cin >> N >> Q;

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

    for(int i=0; i<Q; i++) {
        int p, x; cin >> p >> x;
        p--;
        mark[p] += x;
    }

    dfs(G, mark, ans, 0, 0);

    for(int i=0; i<N; i++) {
        cout << ans[i] << " \n"[i + 1 == N];
    }
    return 0;
}


Measured memory_bytes: 32128
#include <iostream>
#include <vector>
using namespace std;
int N;
int getMax(vector<int> A,int n)
{
	int i;
	int x=A[n];
	A[n]=0;
	int maxA=0;
	for (i=0;i<N;i++){
		if (maxA<A[i]){
			maxA=A[i];
		}
	}
	A[n]=x;
	return maxA;
}
int main(int argc, char* argv[])
{
	int i;
	cin>>N;
	vector<int> A(N);
	int MaxA=0;
	int MaxA1=0;
	for (i=0;i<N;i++){
		cin>>A[i];
		if (MaxA<A[i]){
			MaxA=A[i];
		}
	}
	for (i=0;i<N;i++){
		if (MaxA==A[i]){
			if (MaxA1==0){
				MaxA1=getMax(A,i);
			}
			cout<<MaxA1<<endl;
		}else{
			cout<<MaxA<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3200
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        """
        return self._sizes[self.root(x)]


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

# from libs.debug import plot_graph
#
# plot_graph(VU)

graph = [[] for _ in range(N)]
for v, u in VU:
    v -= 1
    u -= 1
    graph[v].append(u)
    graph[u].append(v)

reqs = [max(a, b) for a, b in zip(A, B)]
uses = list(B)

idx = argsort([a - b for a, b in zip(A, B)])
uf = UnionFind(size=N)
seen = [False] * N
ans = [INF] * N
for v in idx:
    seen[v] = True
    roots = set()
    for u in graph[v]:
        if not seen[u]:
            continue
        roots.add(uf.root(u))

    use_all = uses[v]
    for r in roots:
        use_all += uses[r]

    # v が最後
    req_v = reqs[v] + use_all - uses[v]
    for r in roots:
        req_v = min(req_v, max(reqs[r], reqs[v] - uses[v]) + use_all - uses[r])

    for r in roots:
        uf.unite(v, r)
    reqs[uf.root(v)] = req_v
    uses[uf.root(v)] = use_all
ans = reqs[uf.root(0)]
print(ans)


Measured memory_bytes: 127928
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)

#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007LL
#define INF 2000000000
#define PI 3.1415926

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

typedef long long ll;

template <typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T> inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

struct UnionFind {
	vector<int> par;

	UnionFind(int size) : par(size, -1){}
	void init(int n){ par.assign(n, -1); }

	int find(int x){
		if(par[x] < 0) return x;
		else return par[x] = find(par[x]);
	}
	bool same(int x, int y){
		return find(x)==find(y);
	}
	bool unite(int x, int y){
		x = find(x); y = find(y);
		if(x == y) return 0;
		if(par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return 1;
	}
	int size(int x){
		return -par[find(x)];
	}
};

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

	int n, m, a[100000], b[100000]; cin >> n >> m;
	REP(i, m){
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
	}
	UnionFind uf(n);
	vector<ll> ans;
	ll num = 1LL*n*(n-1)/2;
	for(int i = m-1; i >= 0; i--){
		ans.pb(num);
		if(uf.same(a[i], b[i])) continue;

		num -= 1LL*uf.size(a[i])*uf.size(b[i]);
		uf.unite(a[i], b[i]);
	}
	for(int i = ans.size()-1; i >= 0; i--){
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 3444
#include<bits/stdc++.h>
using namespace std;
#define io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define ss second
#define ff first
#define pii pair<int,int> 
#define mp make_pair()
int main(){
    int n,a,b;
  cin>>n>>a>>b;
  if(n*a<=b) cout<<n*a;
  else cout<<b;
}

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

int main() {
	long long n,a,b;
	cin >> n >> a >> b;
	long long k=0,mx=a+(b*(n-1)),mn=b+(a*(n-1));
	if(a > b)
	{
		k = 0;
	}
	else if(a == b)
	{
		k = 1;
	}
	else if(a < b)
	{
		if(n == 1)
		{
			k = 0;
		}
		else
		{
			k = mx - mn + 1;
		}
	}
    cout << k << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;

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

int main(){
    int h,w;
    cin >> h >> w;
    vector<string>s(h);
    REP(i,h)cin >> s[i];
    bool visited[h][w];
    REP(i,h)REP(j,w)visited[i][j]=false;

    queue<pair<pair<int,int>,char>>que;
    vector<ll>black,white;
    ll answer=0;
    REP(i,h){
        REP(j,w){
            if(s[i][j]=='#' and !visited[i][j]){
                que.push(make_pair(make_pair(i,j),'#'));
                ll blackcount=0,whitecount=0;
                while(!que.empty()){
                    int y,x;
                    char color,nextcolor;
                    y=que.front().first.first;x=que.front().first.second;color=que.front().second;
                    que.pop();
                    visited[y][x]=true;
                    if(color=='#'){
                        blackcount++;
                        nextcolor='.';
                    }
                    else {
                        whitecount++;
                        nextcolor='#';
                    }
                    int nexty,nextx;
                    REP(k,4){
                        nexty=y+dy[k];
                        nextx=x+dx[k];
                        if(nexty >= 0 and nexty < h and nextx >= 0 and nextx < w){
                            if(s[nexty][nextx]==nextcolor and !visited[nexty][nextx]){
                                que.push(make_pair(make_pair(nexty,nextx),nextcolor));
                                visited[nexty][nextx]=true;
                            }
                        }
                    }
                }
                black.push_back(blackcount);
                white.push_back(whitecount);
            }
        }
    }
    REP(i,black.size()){
        answer+=black[i]*white[i];
    }
    
    
    
    /*REP(i,black.size()){
        cout << black[i] << " ";
    }
    cout << endl;
    REP(i,white.size()){
        cout << white[i] << " ";
    }
    cout << endl;*/

    /*REP(i,h){
        REP(j,w){
            cout << visited[i][j] << " ";
        }
        cout << endl;
    }*/
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 6636
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin>>n;
    string s;
    long long int cou=1;
    long long int ans=0;
    vector<string>v(n);
    for(int i=0; i<n; i++){
        cin>>s;
        sort(s.begin(),s.end());
        v.at(i)=s;
    }
    sort(v.begin(),v.end());
    for(int j=0; j<n-1; j++){
        if(v.at(j)==v.at(j+1)){
            cou++;
        }else{
            ans+=cou*(cou-1)/2;
            cou=1;
        }
    }
    ans+=cou*(cou-1)/2;
    cout<<ans<<endl;
}


Measured memory_bytes: 6436
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k;
  cin >> n >> k;
  vector<int> h(n);
  vector<int> dp(n, INT_MAX);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }

  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= k && i + j < n; j++) {
      int tmp = abs(h[i + j] - h[i]);
      if (dp[i] + tmp < dp[i + j]) {
        dp[i + j] = dp[i] + tmp;
      }
    }
  }
  cout << dp[n - 1] << endl;
  return 0;
}

Measured memory_bytes: 4012
list = []
while True:
    a = [int(i) for i in input().split()]
    if a[0] == 0 and a[1] == 0:
        break
    else:
        list.append(a)

for i in range(len(list)):
    x = "#" * list[i][1]
    y = "#" + "." * (list[i][1] - 2) + "#"
    for j in range(list[i][0]):
        if j == 0 or j == list[i][0] - 1:
            print(x)
        else:
            print(y)
    print("")



Measured memory_bytes: 5628