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

using namespace std;

int main()
{
  int n, m, a;
  while(cin >> n >> m >> a, n || m || a){
    --a;
    int kuji[1000][100];
    for(int i = 0; i < 100; i++){
      for(int j = 0; j < 1000; j++) kuji[j][i] = i;
    }
    for(int i = 0; i < m; i++){
      int h, p, q;
      cin >> h >> p >> q;
      --h, --p, --q;
      kuji[h][p] = q;
      kuji[h][q] = p;
    }
    for(int i = 999; i >= 0; i--){
      a = kuji[i][a];
    }
    cout << a+1 << endl;
  }
  return 0;
}

Measured memory_bytes: 1548
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll n, a, b, x;
  in(n);
  vector<ll> c(100, 1), d;
  x = 0;
  rep(i, n){
    a = i + 1;
    b = 2;
    while(a > 1){
      if(a % b == 0){
        a /= b;
        c[b]++;
      }
      else
        b++;
    }
  }
  rep(i, 100){
    if(c[i] != 1)
      d.pb(c[i]);
  }
  n = d.size();
  rep(i, n){
    if(d[i] >= 75)
      x++;
    rep2(j, i + 1, n){
      if(d[i] >= 15 && d[j] >= 5){
        x++;
      }
      if(d[i] >= 5 && d[j] >= 15){
        x++;
      }
      if(d[i] >= 25 && d[j] >= 3){
        x++;
      }
      if(d[i] >= 3 && d[j] >= 25){
        x++;
      }
      rep2(k, j + 1, n){
        if(d[i] >= 3 && d[j] >= 5 && d[k] >= 5){
          x++;
        }
        if(d[i] >= 5 && d[j] >= 3 && d[k] >= 5){
          x++;
        }
        if(d[i] >= 5 && d[j] >= 5 && d[k] >= 3){
          x++;
        }
      }
    }
  }
  out(x);
  memi;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for(auto v:(V))cout<<v<<" "<<endl
inline int GCD(int a, int b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;

int mzero(int x)
{
    return max(0,x);
}
int main()
{
    int H, W, N, sr, sc;
    string S, T;
    cin >> H >> W >> N >> sr >> sc >> S >> T;

    int uout = 0, dout = 0, lout = 0, rout = 0;

    for(int i = N-1; i >= 0; i--)
    {
        if (T.at(i) == 'L')
        {
            rout = mzero(rout-1);
        }
        if (T.at(i) == 'R')
        {
            lout = mzero(lout - 1);
        }
        if (T.at(i) == 'U')
        {
            dout = mzero(dout - 1);
        }
        if (T.at(i) == 'D')
        {
            uout = mzero(uout - 1);
        }
        if (S.at(i) == 'L')
        {
            lout++;
        }
        if (S.at(i) == 'R')
        {
            rout++;
        }
        if (S.at(i) == 'U')
        {
            uout++;
        }
        if (S.at(i) == 'D')
        {
            dout++;
        }
        if(lout + rout >= W || uout + dout >= H)
        {
            std::cout << "NO" << endl;
            return 0;
        }
    }
    if(lout >= sc || rout >= W-sc+1 || uout >= sr || dout >= H-sr+1)
    {
        std::cout << "NO" << endl;
    }
    else
    {
        std::cout << "YES" << endl;
    }

}

Measured memory_bytes: 776
using System;
using CompLib.Util;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int h = sc.NextInt();
        int w = sc.NextInt();
        int k = sc.NextInt();
        string[] c = new string[h];
        for (int i = 0; i < h; i++)
        {
            c[i] = sc.Next();
        }

        int lR = 1 << h;
        int lC = 1 << w;
        int ans = 0;
        for (int i = 0; i < lR; i++)
        {
            for (int j = 0; j < lC; j++)
            {
                int cnt = 0;
                for (int l = 0; l < h; l++)
                {
                    for (int m = 0; m < w; m++)
                    {
                        if (c[l][m] == '#' && (i & (1 << l)) == 0 && (j & (1 << m)) == 0)
                        {
                            cnt++;
                        }
                    }
                }

                if (cnt == k) ans++;
            }
        }

        Console.WriteLine(ans);
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            if (_index >= _line.Length)
            {
                string s;
                do
                {
                    s = Console.ReadLine();
                } while (s.Length == 0);

                _line = s.Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public string ReadLine()
        {
            _index = _line.Length;
            return Console.ReadLine();
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            string s = Console.ReadLine();
            _line = s.Length == 0 ? new string[0] : s.Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 27440
#include <bits/stdc++.h>
#include <stdlib.h>
#include <time.h> 
 
using namespace std;
long long mod = 1e9 + 7;
long long INF = 1e7;
double EPS = 1e-12;
typedef long long int lld;
long double tick(){static clock_t oldt; clock_t newt=clock();
    long double diff=1.0L*(newt-oldt)/CLOCKS_PER_SEC; oldt = newt; return diff; }
#define rep(i,a,n) for(long long int i = (a); i <= (n); ++i)
#define repI(i,a,n) for(int i = (a); i <= (n); ++i)
#define repD(i,a,n) for(long long int i = (a); i >= (n); --i)
#define repDI(i,a,n) for(int i = (a); i >= (n); --i)
inline lld sc() { lld a; scanf("%lld", &a); return a; }
inline int scd() { int a; scanf("%d", &a); return a; }
inline double scf() { double a; scanf("%lf",&a); return a; }
#define prL(a) printf("%lld\n",a)
#define prS(a) printf("%lld ",a)
#define prdL(a) printf("%d\n",a)
#define prdS(a) printf("%d ",a)
#define all(c) (c).begin(), (c).end()
#define sz(a) ((int)a.size())
#define Error(x...) { cout << "(" << #x << ")" << " = ( "; printIt(x); }
template <typename T1> void printIt(T1 t1) { cout << t1 << " )" << endl; }
template <typename T1, typename... T2>
void printIt(T1 t1, T2... t2) { cout << t1 << " , "; printIt(t2...); }
#define errorpair(a) cout<<#a<<" = ( "<<((a).first)<<" , "<<((a).second)<<" )\n";
#define mset(a, v) memset(a, v, sizeof(a))
#define popcount __builtin_popcountll

typedef pair<lld,lld> PA;

lld powP(lld x, lld y) {
    lld ans = 1, po = x % mod;
    while(y > 0) {
        if(y & 1) ans = ans * po % mod;
        y >>= 1; po = po * po % mod;
    }
    return ans;
}
 
bool bitSet(lld n, lld bit){
    if((n & (1LL << bit)) != 0) return true;
    else return false;
}
 
lld findGcd(lld a, lld b){
    while(a != 0) { lld temp = b % a; b = a; a = temp; }
    return b;
}

#define lim 300010
#define lim2 200010
#define qqqqqq 210
// Ab :)
// inline lld sqr(lld x) { return x * x; }
// unordered_map<lld,lld>::iterator it;
// std::ios::sync_with_stdio(false);
// priority_queue<PA> Q;
// lld dp[1<<18];

// vector<lld> G[lim];
// string S[lim];
// lld A[lim],B[lim],C[lim];

int main(){
    lld k = sc();
    lld a = sc(), b = sc();
    rep(i,a,b) if(i % k == 0) {
        printf("OK\n");
        return 0;
    }
    printf("NG\n");
    return 0;
}


Measured memory_bytes: 3760
import java.util.*;
import static java.lang.Integer.*;
//import static java.lang.Long.*;
//import static java.lang.Math.*;
import static java.lang.System.*;

import java.io.PrintWriter;

public class Main {
	public static void main(String[] args) {
		int i, j, k;
		Scanner sc = new Scanner(System.in);
		int n = parseInt(sc.next());
		int m = parseInt(sc.next());
		Py[] py = new Py[m];
		int[] p = new int[m];
		for(i = 0; i < m; i++) {
			p[i] = parseInt(sc.next());  
			py[i] = new Py(i, p[i],parseInt(sc.next()));
		}
		sc.close();
		Arrays.sort(py, (a, b) -> {if(a.p != b.p) {
			return a.p - b.p;
		} else {
			return a.y - b.y;
		}
		});
		int prep = -1;
		int xx = 0;
		int[] x = new int[m];
		for(i = 0; i < m; i++) {
			if(prep == py[i].p) {
				xx++;
			} else {
				prep = py[i].p;
				xx=1;
			}
			x[py[i].m] = xx;
		}
//		Arrays.sort(py, (a, b) -> a.m - b.m);
		PrintWriter out = new PrintWriter(System.out);
		for(i = 0; i < m; i++) {
			out.printf("%06d%06d%n", p[i], x[i]);
		}
		out.flush();
	}
}
class Py {
	int p;
	int y;
	int m;
	Py(int m, int p, int y){
		this.m = m;
		this.p = p;
		this.y = y;
	}
}


Measured memory_bytes: 102352
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
typedef complex<double> P;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 29;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };

int n, m;
bool can_use;
set<int> a;
int dp[ 100001 ][ 2 ];
int ans = 0;

int solve( int now, bool used ) {
	if ( now > n ) {
		return 0;
	}
	if ( dp[ now ][ used ] >= 0 ) {
		return dp[ now ][ used ];
	}
	int res = 0;
	if ( a.count( now ) ) {
		res = max( res, solve( now + 1, used ) + 1 );
	}
	else {
		if ( used ) {
			res = max( res, solve( now + 1, used - 1 ) + 1 );
		}
		else {
			return dp[ now ][ used ] = 0;
		}
	}
	return dp[ now ][ used ] = res;
}

int main() {
	while ( ~scanf( "%d %d", &n, &m ) && n && m ) {
		NCLR( dp );
		can_use = false;
		for ( int i = 0; i < m; i++ ) {
			int b;
			scanf( "%d", &b );
			if ( b ) {
				a.insert( b );
			}
			else {
				can_use = true;
			}
		}
		ans = 0;
		for ( int i = 1; i <= n; i++ ) {
			if ( a.count( i - 1 ) == 1 && a.count( i ) ) {
				continue;
			}
			ans = max( ans, solve( i, can_use ) );

		}
		printf( "%d\n", ans );
		a.clear();
	}
	return 0;
}

Measured memory_bytes: 5668
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int X = in.nextInt();
        int T = in.nextInt();
        int ans = snack(N, X, T);
        System.out.println(ans);

    }

    // 20, 12, 6
    public static int snack(int N, int X, int T) {
        int x = X;
        int t = T;
        for (; x < N; x = x + X) {
            t = t + T;
        }
        return t;
    }
}


Measured memory_bytes: 35672
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1000*1007;
const ll mod=1000*1000*1000+7;
const ll inf=1e18;

int n;

vi graf[nax];

ll tak[nax];
ll nie[nax];

void dfs(int v, int oj)
{
	tak[v]=1;
	nie[v]=1;
	for (int i : graf[v])
	{
		if (i==oj)
			continue;
		dfs(i, v);
		ll ta=tak[v];
		ll ni=nie[v];
		tak[v]=(ta*nie[i])%mod;
		nie[v]=(ni*(nie[i]+tak[i]))%mod;
	}
}

int main()
{
	scanf("%d", &n);
	for (int i=1; i<n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		graf[a].push_back(b);
		graf[b].push_back(a);
	}
	dfs(1, 0);
	printf("%lld\n", (tak[1]+nie[1])%mod);
	return 0;
}


Measured memory_bytes: 36224
n = int(raw_input())
a = []
for i in range(n):
    a.append(int(raw_input()))

cnt = 0
num = 1
G = [1]
while 1:
    if num*3+1 > n:
        break
    G.insert(0, num*3+1)
    num = num*3 + 1
m = len(G)

def insertionSort(A, n, g, cnt):
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt

for i in range(m):
    cnt = insertionSort(a, n, G[i], cnt)

print m
for i in range(m):
    if i == m-1:
        print G[i]
    else:
        print G[i],
        
print cnt

for i in range(n):
    print a[i]

Measured memory_bytes: 77576
N = int(input())
abc = [list(map(int,input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0][0] = abc[0][0]
dp[0][1] = abc[0][1]
dp[0][2] = abc[0][2]
for i in range(N-1):
    dp[i+1][0] = max(dp[i+1][0],dp[i][1]+abc[i+1][0],dp[i][2]+abc[i+1][0])
    dp[i+1][1] = max(dp[i+1][1],dp[i][0]+abc[i+1][1],dp[i][2]+abc[i+1][1])
    dp[i+1][2] = max(dp[i+1][2],dp[i][0]+abc[i+1][2],dp[i][1]+abc[i+1][2])

print(max(dp[N-1]))

Measured memory_bytes: 75192
#include <iostream>

using namespace std;

int N, K;

int main() {
  int sum = 0, x;
  scanf("%d %d", &N, &K);
  for (int i = 0; i < N; i++) {
    scanf("%d", &x);
    if (x < K - x) {
      sum += x * 2;
    } else {
      sum += (K - x) * 2;
    }
  }
  printf("%d\n", sum);

  return 0;
}


Measured memory_bytes: 256
from collections import Counter

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

c1 = Counter(v[::2])
c2 = Counter(v[1::2])
c1[0] = 0
c2[0] = 0
c1 = sorted(c1.items(), key=lambda x: x[1], reverse=True)
c2 = sorted(c2.items(), key=lambda x: x[1], reverse=True)

if c1[0][0] != c2[0][0]:
    ans = n - c1[0][1] - c2[0][1]
else:
    ans = min(n - c1[0][1] - c2[1][1], n - c2[0][1] - c1[1][1],)
print(ans)


Measured memory_bytes: 18656
n = int(input())

count = 0
ans = "No"

for i in range(n):
    query = list(map(int, input().split()))
    
    if query[0] == query[1]:
        count = count + 1
        if count == 3 :
            ans = "Yes"
    else :
        count = 0

print(ans)

Measured memory_bytes: 9172
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>
#include <cassert>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX;
const ll MOD = 1e9+7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;cin>>N;
  vll A(N),B(N),dif(N);
  ll sumA=0,sumB=0;
  repeat(i,N){
    cin >>A[i];
    sumA+=A[i];
  }
  repeat(i,N){
    cin>>B[i];
    sumB+=B[i];
  }
  if(sumA<sumB){
    cout << -1 << endl;
    return 0;
  }
  repeat(i,N){
    dif[i] = A[i]-B[i];
  }
  sort(dif.begin(),dif.end());
  dif.push_back(0);
  ll ans = 0;
  ll j=N;
  repeat(i,N){
    if(dif[i]>=0)break;
    ans++;
    dif[j] += dif[i];
    if(dif[j]<0){
      ans++;
      j--;
      dif[j]+=dif[j+1];
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main () {
  int n;
  cin >> n;
  long long a[n];
  for(int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i] -= i;
  }
  sort(a,a+n);
  long long	sum = 0;
  for(int i=0; i<n; ++i) {
    sum += abs(a[i]-a[n/2]);
  }
  cout << sum;
}


Measured memory_bytes: 1792
import std.stdio, std.string, std.conv, std.algorithm, std.math;
void main() {
	for (;;) {
		auto n = readln.chomp.to!real;
		if (n == 0) break;
		auto d = readln.split.to!(real[]);
		real s = d.reduce!"a + b";
		real av = s / n;
		real r = d.map!(a => (a - av).pow(2)).sum / n;
		"%.8f".writefln(r.sqrt);
	}
}

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

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

const ll INF = 1e18;

int main() {
	int n, m;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) break;
		vector<int> c(m);
		rep(i, m) cin >> c[i];
		vector<int> x(n);
		rep(i, n) cin >> x[i];
		
		vector<vector<ll>> dp(n + 1, vector<ll>(256, INF));
		dp[0][128] = 0;
		
		rep(i, n) {
			rep(j, 256) {
				if (dp[i][j] == INF) continue;
				rep(k, m) {
					int y = max(0, min(255, j + c[k]));
					ll p = pow(y - x[i], 2);
					chmin(dp[i + 1][y], dp[i][j] + p);
				}
			}
		}
		
		ll ans = INF;
		rep(i, 256) chmin(ans, dp[n][i]);
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 43808
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

ll modpow(ll a, ll n, ll modo) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % modo;
        a = a * a % modo;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

map<ll, ll> prime_factor(ll n){
    map<ll, ll> mp;
    for(int i = 2; i * i <= n; i++){
        while(n % i == 0){
            mp[i]++;
            n /= i;
        }
    }
    if(n != 1)mp[n]++;
    return mp;
}

int main() {
    ll n, ans = 0, l = 1;
    cin >> n;
    vector<ll> a(n);
    map<ll, ll> mp;
    rep(i, n){
        cin >> a[i];
        map<ll, ll> p = prime_factor(a[i]);
        for(auto x : p){
            mp[x.first] = max(mp[x.first], x.second);
        }
    }
    for(auto x : mp)l = l * modpow(x.first, x.second, mod) % mod;
    rep(i, n){
        ll now = l * modinv(a[i], mod) % mod;
        ans = (ans + now) % mod;
    }
    cout << ans << endl;
}


Measured memory_bytes: 896
#include <iostream>
#include <set>

int main() {
  std::multiset<int> tmp;
  int A;
  int B;
  int C;

  std::cin >> A >> B >> C;
  tmp.insert(A);
  tmp.insert(B);
  tmp.insert(C);

  for (int x : tmp) {
    std::size_t n = tmp.count(x);
    if (n == 1) {
      std::cout << x << std::endl;
      break;
    }
  }
  return 0;
}

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

using namespace std;

int n, Head[M], Next[M], Go[M], C[M], Ans[M], Deg[M], Cnt = 0;

void addedge(int x, int y) {Go[++Cnt] = y, Next[Cnt] = Head[x], Head[x] = Cnt;}

int main() {
	scanf("%d", &n);
	for(int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		addedge(a, b), addedge(b, a), Deg[a]++, Deg[b]++;
	}
	vector <int> V(0);
	for(int i = 1; i <= n; i++) if(Deg[i] <= 1) V.push_back(i);
	for(int i = 1; i <= n; i++) scanf("%d", &C[i]);
	sort(C + 1, C + n + 1);
	int ans = 0;
	for(int i = 0; i < V.size(); i++) {
		int x = V[i];
		Ans[x] = C[i + 1];
		ans += Deg[x] * C[i + 1];
		for(int T = Head[x]; T; T = Next[T]) if(--Deg[Go[T]] == 1) V.push_back(Go[T]);
	}
	printf("%d\n", ans);
	for(int i = 1; i <= n; i++) printf("%d ", Ans[i]);
	return 0;
}

Measured memory_bytes: 2560
N,M = map(int, input().split())

if M <= 0:
    print("0 0")
    exit(0)

exactly = 0
penarty = 0
scores = {}

for i in range(M):
    p,s = input().split()
    p = int(p) - 1

    if scores.get(p) is None:
        scores[p] = {"AC":0, "WA":0}
    elif scores[p]["AC"] > 0:
        continue

    if s == "AC":
        scores[p]["AC"] = 1
        exactly += 1
        penarty += scores[p]["WA"]

    elif s == "WA":
        scores[p]["WA"] += 1

print("{0} {1}".format(exactly, penarty))

Measured memory_bytes: 42088
<?php
 
while($line = fgets(STDIN)){
    $d = intval($line);
    $s = 0;
    
    // ??¬????????????
    // S = 1/6*n*(n + 1)*(2*n + 1);
    
	$n = 600/$d - 1;
	$s = $d*$d*$d*$n*($n + 1)*(2*$n + 1)/6;
	
	$s = 100*(600 - $d)*(1200 - $d);
	
    echo $s."\n";
}

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


int main() {
    string s, t;
    cin >> s >> t;

    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());

    if (s < t) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3616
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif


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

    int H, W; cin >> H >> W;
    vs A(H); REP(i, H) cin >> A[i];

    queue<int> qx, qy;
    vvi grid(H, vi(W, -1));
    REP(i,H){
        REP(j,W) {
            if (A[i][j]=='#'){
                qx.push(i);
                qy.push(j);
                grid[i][j] = 0;
            }
        }
    }

    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    while (!qx.empty()) {
        int x = qx.front(); qx.pop();
        int y = qy.front(); qy.pop();

        REP(k,4) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0<=nx && nx < H && 0<=ny && ny < W && grid[nx][ny]<0) {
                qx.push(nx);
                qy.push(ny);
                grid[nx][ny] = grid[x][y] + 1;
            }
        }
    }

    int ans = -INF;
    REP(i,H){
        REP(j,W) {
            ans = max(ans, grid[i][j]);
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 13440
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int_fast64_t S, i;
    cin >> S;
    i = sqrt(S);
    if (i*i < S) i++;
    printf("0 0 1 %d %d %d\n", i, i, i*i-S);
    return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(15);

  int a, b, k;
  cin >> a >> b >> k;

  int cnt = 0;
  for (int i = min(a,b); i >= 0; --i) {
    if (a % i == 0 && b % i == 0) {
      ++cnt;
      cerr << i << '\n';
      if (cnt == k) {
        cout << i << '\n';
        break;
      }
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef double lld;
#define mod 1000000007
#define mod2 998244353
#define fori(n) for (int i = 0; i < n; i++)
#define forj(n) for (int j = 0; j < n; j++)
#define pb push_back
#define F first
#define S second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
template <typename T, typename U>ostream &operator<<(ostream &out, const pair<T, U> &p){out << "(" << p.first << ", " << p.second << ")";return out;}
template <template <typename, typename...> class ContainerType, typename ValueType, typename... Args>void print(const ContainerType<ValueType, Args...> &c){for (const auto &v : c)cout << v << ' ';cout << '\n';} void print(){cout<<'\n';}
template <typename T, typename... Args>void print(T a, Args... args){cout << a << " ";print(args...);}
lli llipower(lli x, lli y, lli p = LLONG_MAX){lli res = 1;x = x % p;while (y > 0){if (y & 1)res = (res * x) % p;y = y >> 1;x = (x * x) % p;}return res;}

//8====================================D
int main(){
    lli n,m,k;
    cin>>n>>m>>k;
    vector<lli> a(n);
    vector<lli> b(m);
    fori(n) cin>>a[i];
    fori(m) cin>>b[i];
    vector<lli> pra(n+1,0);
    vector<lli> prb(m+1,0);
    lli curr=0;
    for(int i=0;i<n;i++){
        curr+=a[i];
        pra[i+1]=curr;
    }
    curr = 0;
    for (int i = 0; i < m; i++)
    {
        curr += b[i];
        prb[i + 1] = curr;
    }
    lli ans=0;
    lli rem=0;
    for(int i=0;i<n+1;i++){
        
        curr=pra[i];
        if(curr>k) break;
        rem=k-curr;
        lli pos=lower_bound(prb.begin(),prb.end(),rem)-prb.begin();
        if(prb[pos]>rem || pos == prb.size()) pos--;
        ans=max(ans,i+pos);

    }
    cout<<ans<<endl;
}

Measured memory_bytes: 9592
n,a,b = map(int,input().split())
mod = 10 ** 9 + 7

# 乗法のmod逆元 (mod-2乗)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    x = 1
    y = 1
    for i in range(r):
        x *= (n - i)
        y *= (i + 1)
        x %= mod
        y %= mod
    return (x * modinv(y, mod)) % mod

ans = pow(2, n, mod)
ans -= combination(n,a) + combination(n,b) + 1

print(ans % mod)


Measured memory_bytes: 38640
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <algorithm>
#include <iomanip> //cout << fixed << setprecision(12) << ans << endl;
using namespace std;
 
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define loop(i, l, r) for(int i = l; i < r; i++)
#define rloop(i, l, r) for(int i = l; i >= 0; i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vec_i;

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int INF = 1e9;
const int MOD = 1e9+7;

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

	priority_queue<int> q;
	rep(i, n){
		int a;
		cin >> a;
		q.push(a);
	}
	rep(i, m){
		int b = q.top();
		q.pop();
		q.push(b/2);
	}
	ull ans = 0;
	rep(i, n){
		ans += q.top();
		q.pop();
	}
	cout << ans << endl;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
#define pb push_back
#define debug(x) cout << x << endl
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
#define PI acos(-1)
#define all(c) c.begin(), c.end()
#define SET(x, y) memset((x), y, sizeof(x))
const int MOD = 1e9 + 7;
const int INF = 1e9 + 5;
const LL INF64 = 1e18;

const int N = 1e5 + 5;

string s;

int main() {
	fastio;
	cin >> s;
	int ans1 = 0;
	int ans2 = 0;
	int now = 0;
	int sz = s.size();
	for (int i = 0; i < sz; i++) {
		if (s[i] - '0' != now)
			ans1++;
		now = now ^ 1;
	}
	now = 1;
	for (int i = 0; i < sz; i++) {
		if (s[i] - '0' != now)
			ans2++;
		now = now ^ 1;
	}
	cout << min(ans1, ans2) << endl;
	return 0;
}
		

Measured memory_bytes: 512
d = int(input())
c = list(map(int, input().split()))
prev = [0] * 26
# 毎日コストの最小化を試みてみる
for i in range(d):
  s = list(map(int, input().split()))
  cost = 10 ** 10
  ans = -1
  for j in range(26):
    tmp = 0
    for k in range(26):
      if j == k:
        continue
      tmp += c[k] * (i - prev[k])
    if tmp < cost:
      cost = tmp
      ans = j
  prev[ans] = i
  print(ans+1)


Measured memory_bytes: 75384
import sys

def solve():
    readline = sys.stdin.readline
    H, W, M = map(int, readline().split())
    h = [0] * H
    w = [0] * W
    b = set()
    for _ in range(M):
        y, x = map(int, readline().split())
        x -= 1
        y -= 1
        h[y] += 1
        w[x] += 1
        b.add(y*W+x)
    h = sorted(zip(h, range(H)), reverse=True)
    ans = 0
    for i in range(W):
        x = w[i]
        for y, j in h:
            if x+y > ans:
                if j*W+i in b:
                    ans = x+y-1
                else:
                    ans = x+y
                    break
            else:
                break
    print(ans)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 68500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    if (A == B)
    {
        cout << C << endl;
    }
    else if (B == C)
    {
        cout << A << endl;
    }
    else
    {
        cout << B << endl;
    }
}

Measured memory_bytes: 256
sx,sy,tx,ty=map(int,input().split())
dx = tx - sx
dy = ty - sy
direction1 = 'U'*dy + 'R'*dx 
direction2 = 'D'*dy + 'L'*dx
direction3 = 'L' + 'U'*(dy+1) + 'R'*(dx+1) + 'D'
direction4 = 'R' + 'D'*(dy+1) + 'L'*(dx+1) + 'U'
print(direction1+direction2+direction3+direction4)

Measured memory_bytes: 9196
N = int(input().strip())
A = list(map(int, input().strip().split()))[::-1]
B = list(map(int, input().strip().split()))[::-1]

total = 0
for i in range(N):
  b = B[i]
  a = A[i]

  if a >= b:
    total += b
    continue

  total += a
  b -= a

  a = A[i + 1]
  if a >= b:
    total += b
    A[i + 1] = a - b
  else:
    total += a
    A[i + 1] = 0

print(total)

Measured memory_bytes: 18624
l = ['11', '31', '41', '61', '71', '101', '131', '151', '181', '191',
'211', '241', '251', '271', '281', '311', '331', '401', '421', '431',
'461', '491', '521', '541', '571', '601', '631', '641', '661', '691',
'701', '751', '761', '811', '821', '881', '911', '941', '971', '991',
'1021', '1031', '1051', '1061', '1091', '1151', '1171', '1181', '1201',
'1231', '1291', '1301', '1321', '1361', '1381']
print(' '.join(l[:int(input())]))

Measured memory_bytes: 9076
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>
#include <chrono>
#include <sstream>
#include <iomanip>

#define INF 1 << 30
#define MOD 1000000007;
#define PI 3.14159265358979
#define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)
#define reu(i, l, r) for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define D(x) cout << x << endl
#define d(x) cout << x
#define all(x) (x).begin(), (x).end()
#define pub(x) push_back(x)
#define pob() pop_back()
#define puf(x) push_front(x)
#define pof() pop_front()
#define mp(x, y) make_pair((x), (y))
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }

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

int main() { 
  int n;
  cin >> n;
  string s;
  int cnt[55][128];
  rep (i, 55) rep (j, 128) cnt[i][j] = 0;
  rep (i, n) {
    cin >> s;
    rep (j, s.size()) {
      cnt[i][s[j]]++;
    }
  }

  int mins[128];
  rep (i, 128) mins[i] = INF;

  rep (i, 128) {
    rep (j, n) {
      amin(mins[i], cnt[j][i]);
    }
  }

  //rep (i, 128) {
  //  D(mins[i]);
  //}

  
  rep (i, 128) {
    rep (j, mins[i]) {
      char a;
      a = i;
      d(a);
    }
  }
  D("");

  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

int main(int argc, char const* argv[])
{
    int r, d, x_2000;
    std::cin >> r >> d >> x_2000;;

    for(int i=0; i<10;++i)
    {
        int next = r * x_2000 - d;
        x_2000 = next;
        std::cout << next << std::endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s,t;
	cin>>s>>t;
	for(int i=0;i<s.size();i++)
	    if(s[i]!=t[i]){
	    	cout<<"No";
	    	return 0;
		}
	cout<<"Yes";
	return 0;
}

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

using namespace std;
const int maxn = 55555;
int v[maxn+10];
int p[maxn];
int f(){
	int n = 0;
	for(int i = 2; i < maxn; i++){
		if(!v[i]) p[n++] = i;
		for(int j = 0; j < n && i*p[j] < maxn; j++){
			v[i*p[j]] = 1;
			if(i%p[j] == 0) break;
		}
	}
	return n;
}


int main(int argc, char const *argv[])
{
	//freopen("in.txt", "r", stdin);
	int q;
	scanf("%d", &q);
	int n = f();
	printf("11");
	int cnt = 1;
	for(int i = 5; i < n ; i++){
		if(p[i]%5 == 1) {
			printf(" %d", p[i]);
			if(++cnt >= q) break;
		}
	}
	putchar(10);
	return 0;
}

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

int main(){
	int n, x, sum = 0;
	std::vector<int> a;
	std::vector<int> b;
	std::vector<int> c;
	std::cin >> n;
	for(int i = 0; i < n; i++){
		std::cin >> x;
		a.push_back(x);
	}
	for(int i = 0; i < n; i++){
		std::cin >> x;
		b.push_back(x);
	}
	for(int i = 0; i < n - 1; i++){
		std::cin >> x;
		c.push_back(x);
	}
	for(int i = 0; i < n; i++){
		if(i == 0) sum += b[a[i] - 1];
		else{
			sum += b[a[i] - 1];
			if(a[i] - 1 == a[i - 1]) sum += c[a[i - 1] - 1];
		}
	}
	std::cout << sum << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define dump(x) cout << #x << " = " << (x) << endl;
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;

  long long ans = 0;
  for(int i = 1; i < n + 1; i++) {
    long long amari = k - (i % k);
    long long va = ((n - amari) / k) + 1;
    if(amari * 2LL % k == 0LL) ans += va * va;
  }
  cout << ans << endl;

  return 0;
}

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

int main(){
    short n;
    string s;
    cin>>n>>s;
    s=" "+s;
    if (n&1) cout<<"No";
    else{
        bool k=true;
        for (short i=1,j=n/2+1;j<=n;++i,++j)
        if (s[i]!=s[j]) {k=false;break;}
        if (k) cout<<"Yes"; else cout<<"No";
    }
}


Measured memory_bytes: 256
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n,m = na()

if n==1 and m==1:
    ura = 1
elif n == 1:
    ura = m-2
elif m == 1:
    ura = n-2
elif n == 2:
    ura = 0
elif m == 2:
    ura = 0
else:
    ura = (n-2)*(m-2)
print(ura)


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

#define int long long
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; }
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define COUT(x) cout << x << endl;
#define PB(x) push_back(x)
#define MP make_pair
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int INF = 1e9;
const int MOD = 1e9+7;

signed main(){
    int n,k; cin >> n >> k;
    vector<int> a(n+1);
    rep(i,n) cin >> a[i+1];

    if(k<1e7){
        int pos=1;
        rep(i,k){
            pos=a[pos];
        }
        cout<<pos<<endl;
        return 0;
    }

    vector<int> dist(n+1,-1);
    dist[1]=0;
    int pos=1;
    rep(i,n){
        if(dist[a[pos]]==-1){
            dist[a[pos]]=dist[pos]+1;
        }
        pos=a[pos];
    }
    //cout<<endl;
    for(int i=1; i<=n; i++){
        //cout<<dist[i]<<" "<<endl;
    }
    vector<bool> visit(n+1,false);
    visit[1]=true;
    pos=1;
    int T;
    int start;
    rep(i,n){
        
        if(visit[a[pos]]==true){
            T=abs(dist[pos]-dist[a[pos]])+1;
            start=a[pos];
            break;
        }
        pos=a[pos];
        visit[pos]=true;
    }
    //cout<<T<<endl;
    int go=(k-dist[start])%T;
    pos=start;
    rep(i,go){
        pos=a[pos];
    }
    cout<<pos<<endl;







    /*
    vector<int> 
    int pos=1;
    int T=0;
    vector<int> visited;
    visited.add(1);
    while(true){
        pos=a[pos];

        visited.add(pos);
        T++;
        if(pos==1) break;
    }
    //cout<<T<<endl;
    int num=k%T;
    rep(i,num){
        pos=a[pos];
    }
    cout<<pos<<endl;
    */

}

Measured memory_bytes: 6376
class ReRooting(object):
    """ 全方位木DP """
    def processing(self, in_:list, v:int):
        """ 単項演算(加工) f """
        return [in_[0] + 1]
    
    def merge(self, in1:list, in2:list):
        """ 二項演算(マージ) ・ """
        return [in1[0] * in2[0] % M]

    def adjustment(self, in_:list, v:int):
        """ 単項演算(調整) g """
        return in_
    
    def solve(self):
        """
        計算結果を返す
        
        Ex. [cnt for cnt, _ in self.calc()]
        """
        return [res for [res] in self.calc()]

    def __init__(self, V:int, e:list):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
    
    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    self.edge[w].remove(v)
                    que.append(w)
    
    def bottom_up(self):
        """ Bottom-Up DP """
        accBU = [self.e for _ in range(self.V)]
        resBU = [None] * self.V
        for v in reversed(self.order):
            for c in self.edge[v]:
                accBU[v] = self.merge(accBU[v], self.processing(resBU[c], c))
            resBU[v] = self.adjustment(accBU[v], v)
        return accBU, resBU
    
    def top_down(self, resBU:list):
        """ Top-Down DP """
        accTD = [self.e for _ in range(self.V)]
        resTD = [self.e for _ in range(self.V)]

        for p in self.order:
            ac = self.e if (p == self.order[0]) else self.processing(resTD[p], p)
            for v in self.edge[p]:
                accTD[v] = ac[:]
                ac = self.merge(ac, self.processing(resBU[v], v))
            
            ac = self.e
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                resTD[v] = self.adjustment(accTD[v], v)
                ac = self.merge(ac, self.processing(resBU[v], v))
        return resTD
    
    def calc(self):
        self.topological_sort()
        accBU, resBU = self.bottom_up()
        resTD = self.top_down(resBU)

        res = [None] * self.V
        for v in self.order:
            res[v] = self.e if (v == self.order[0]) else self.processing(resTD[v], v)
            res[v] = self.merge(accBU[v], res[v])
            res[v] = self.adjustment(res[v], v)
        return res

#############################################################
N, M = map(int, input().split())
 
RR = ReRooting(N, [1])
for _ in range(N - 1):
    x, y = map(int, input().split())
    RR.add_edge(x - 1, y - 1)
 
print(*RR.solve(), sep="\n")

Measured memory_bytes: 60960
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    map<pair<int, int>, int> cnt;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        for (int j = -1; j <= 1; ++j) {
            for (int k = -1; k <= 1; ++k) {
                ++cnt[make_pair(a + j, b + k)];
            }
        }
    }
    vector<ll> ans(10);
    ans[0] = (ll)(h - 2) * (ll)(w - 2);
    for (const auto &v : cnt) {
        if (2 <= v.first.first && v.first.first <= h - 1 && 2 <= v.first.second && v.first.second <= w - 1) {
            ++ans[v.second];
            --ans[0];
        }
    }
    for (ll k : ans) {
        cout << k << endl;
    }
    return 0;
}

Measured memory_bytes: 58496
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  string s;
  cin >> s;
  if (s[0] == '>')
    s = "<" + s;
  if (s[s.size() - 1] == '<')
    s += ">";

  vector<ll> v;
  int n = s.size(), c = 0;
  bool b = true;
  rep(i, 0, n) {
    if (b) {
      if (s[i] == '<')
        c++;
      else {
        v.push_back(c);
        c = 1;
        b = !b;
      }
    } else {
      if (s[i] == '>')
        c++;
      else {
        v.push_back(c);
        c = 1;
        b = !b;
      }
    }
  }
  v.push_back(c);

  ll ans = 0;
  rep(i, 1, v.size()) {
    ll maxv = max(v[i], v[i - 1]);
    ll minv = min(v[i], v[i - 1]);
    minv--;
    ans += maxv * (maxv + 1) / 2;
    ans += minv * (minv + 1) / 2;
    i++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 3888
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;
 

vector<ll> inv,fac;

void inverse(ll n){
    //要素数:n+1 (0~n)
    inv[0]=1;
    inv[1]=1;
    for(ll i=2;i<=n;i++){
        inv[i]=(MOD-inv[MOD%i]*(MOD/i))%MOD;
    }
}

void inverse_u(ll n){
    //要素数:n+1 (0~n)
    for(ll i=2;i<=n;i++){
        inv[i]=(inv[i]*inv[i-1])%MOD;
    }
}

void factorial(ll n){
    //要素数:n+1 (0~n)
    fac[0]=1;
    fac[1]=1;
    for(ll i=2;i<=n;i++){
        fac[i]=(fac[i-1]*i)%MOD;
    }
}

ll nCr(ll n,ll r){
    return fac[n]*inv[r]%MOD*inv[n-r]%MOD;
}

ll proinverse(ll x,ll m){
    ll res=1,M=m-2;
    while(M>0){
        if(M&1) res=res*x%m;
        x=x*x%m;
        M>>=1;
    }
    return res;
}

void init_nCr(ll n){
    inv.assign(n+1,0);
    fac.assign(n+1,0);
    inverse(n); inverse_u(n);
    factorial(n);
}

int main(){
	ll n,m,k; cin>>n>>m>>k;
    init_nCr(n*m);
    ll c=nCr(n*m-2,k-2);
    ll xs,ys;
    if(m==1) xs=0;
    else{
        xs=0;
        ll d=n*n%MOD;
        rep(i,m-1){
            ll D=d*(m-i-1)%MOD;
            xs=(xs+D*(i+1))%MOD;
        }
    }
    if(n==1) ys=0;
    else{
        ys=0;
        ll d=m*m%MOD;
        rep(i,n-1){
            ll D=d*(n-i-1)%MOD;
            ys=(ys+D*(i+1))%MOD;
        }
    }
    cout<<(((xs+ys)*c)%MOD+MOD)%MOD<<endl;
}

Measured memory_bytes: 3328
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.time.LocalTime;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;


public class Main {

    public static void main(String[] args) {
    
    	FastScanner scan = new FastScanner();
    	
    	int n = scan.nextInt();
    	int [] a = new int [4];
    			for(int i=0; i<n; i++) {
    		String str = scan.next();
    		if(str.equals("AC")) a[0]++;
    		else if(str.equals("WA")) a[1]++;
    		else if(str.equals("TLE")) a[2]++;
    		else a[3]++;
    	}
    	System.out.println("AC x " + a[0]);
    	System.out.println("WA x " + a[1]);
    	System.out.println("TLE x " + a[2]);
    	System.out.println("RE x " + a[3]);
    	}   
    
    
    static class FastScanner{
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
    	String next() {
    		while(!st.hasMoreTokens())
    			try {
    				st = new StringTokenizer(br.readLine());
    			} catch (IOException e){
    				e.printStackTrace();
    			}
    		return st.nextToken();
    	}
    	
    	int nextInt() {
    		return Integer.parseInt(next());
    	}
    	
    	int [] readArray(int n) {
    		int [] a = new int[n];
    		for(int i=0; i<n ; i++) a[i] = nextInt();
    		return a;
    	}
    	
    	long nextLong() {
    		return Long.parseLong(next());
    	}
    	
    	
    }
    
   
}



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

const int ftq=1000000007;

int n,k;
int a[105];
int dp[105][100005];
int bit[100005];

int sum(int pos){
    int res=0;
    while(pos>0){
        res=(res+bit[pos])%ftq;
        pos-=pos&-pos;
    }
    return res;
}

void add(int pos,int val){
    while(pos<=k+1){
        bit[pos]=(bit[pos]+val)%ftq;
        pos+=pos&-pos;
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    add(1,1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j]=(sum(j+1)-sum(max(0,j-a[i]))+ftq)%ftq;
        }
        memset(bit,0,sizeof(bit));
        for(int j=0;j<=k;j++){
            add(j+1,dp[i][j]);
        }
    }
    cout<<dp[n][k]<<endl;

    return 0;
}

Measured memory_bytes: 40832