akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define REP(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for(ll (i)-1 = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for(ll (i) = (m); (i) < (n); (i)++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define _GLIBCXX_DEBUG

template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;

const double PI = 3.14159265358979323846;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

int main()
{	
    string s;
    cin >> s;
    bool ok = false;
    int l = s.length();

    while(!ok){
        s.pop_back();
        l = s.length();
        if(l % 2 == 1) continue;
        string s1 = s.substr(0, l/2);
        string s2 = s.substr(l/2);
        if(s1 == s2) ok = true;
    }
    cout << l << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
long long A,B,C,D;
  cin >> A >> B >> C >> D;
  long long c = C;
  long long d = D;
  for(int a = 0;c != d;a++){
   if(c < d)d %= c;
    if(d == 0){
     d = c;
      break;
    }
    if(d < c)c %= d;
    if(c == 0){
     c = d;
      
      break;
    }
  }
  
  long long a = (A-1) / C + (A-1) / D - (A-1) / (C * D / c);
  long long b = B / C + B / D - B / (C * D / c);
  cout << (B - A + 1) - (b - a) << endl;
}

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

int main()
{
    int n,temp = 0,ptr=0;
    cin>>n;
    for(int k=1;k<=n;k++){
            int i = k;
    while(i>0){
            temp++;
        i = i/10;
    }
    if(temp % 2 != 0){
        ptr++;
    }
    temp = 0;
    }
    cout<<ptr<<endl;
}


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

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

  ll sum = 0;
  int sign = 1;
  ll count = 0;
  ll ans = LLONG_MAX;
  // if 0   +1
  rep(j, 2){
    if (j == 0) sign = 1;
    else sign = -1;
    sum = 0;
    count = 0;
    rep(i, n){
      sum += a[i];
      if ((sign > 0) && (sum <= 0)){
        count += (1 - sum);
        sum = 1;
      } else if ((sign < 0) && (sum >= 0)){
        count += abs(-1 - sum);
        sum = -1;
      }
      sign = sign == 1 ? -1 : 1;
    }
    if (ans > count) ans = count;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3696
# -*- coding: utf-8 -*-
import math
import copy

def calc_distance(town1, town2):
    distance_pow = (town1[0] - town2[0])**2 + (town1[1] - town2[1])**2
    distance = math.sqrt(distance_pow)
    return distance

def calc(L, done_towns, todo_towns):
    sum = 0
    if len(todo_towns) == 1:
        done_towns.append(todo_towns[0])
        distance = 0
        while(len(done_towns) >= 2):
            first_town = done_towns.pop(0)
            second_town = done_towns[0]
            min_town = min(first_town, second_town)
            max_town = max(first_town, second_town)
            distance += L[min_town*10 + max_town]
        return distance

    for town in todo_towns:
        new_done_towns = copy.copy(done_towns)
        new_todo_towns = copy.copy(todo_towns)
        new_done_towns.append(town)
        new_todo_towns.remove(town)
        sum += calc(L, new_done_towns, new_todo_towns)

    return sum

N = int(input())
town_points = []
for n in range(N):
    (x, y) = (int(i) for i in input().split())
    town_points.append((x, y))

L = [0] * 78

# 全経路
for i in range(N):
    for j in range(i+1, N):
        L[i*10 + j] = calc_distance(town_points[i], town_points[j])

sum_distance = calc(L, [], list(range(N)))
N_factorial = math.factorial(N)
average_distance = sum_distance / N_factorial

print(average_distance)


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

struct coor{
    int y,x;
    coor(){}
    coor(int Y,int X) : y(Y), x(X){}
    bool operator!=(coor a){return y!=a.y||x!=a.x;}
};

int main(){
    int h,w,n; cin>>h>>w>>n;
    vector<coor> check(n+1);
    vector<vector<int>> field(h+2,vector<int>(w+2,1));
    for(int i=1;i<=h;i++) for(int j=1;j<=w;j++){
        char c; cin>>c;
        if(c!='X') field[i][j]=0;
        if(c=='S') check[0]=coor(i,j);
        if(isdigit(c)) check[c-'0']=coor(i,j);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        auto copy=field;
        auto start=check[i];
        auto goal=check[i+1];
        queue<pair<int, coor>> que;
        que.push(make_pair(0,start));
        while(que.front().second!=goal){
            auto dist=que.front().first;
            auto cur=que.front().second;
            que.pop();
            if(copy[cur.y][cur.x]==1) continue;
            copy[cur.y][cur.x]=1;
            for(int j=0;j<4;j++){
                int v[]={1,0,-1,0,1};
                que.push(make_pair(dist+1,coor(cur.y+v[j], cur.x+v[j+1])));
            }
        }
        ans+=que.front().first;
    }
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 10676
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = (ll)(x)-1;0 <= i; i--)
#define reps(i,x) for(ll i = 1; i < (ll)(x)+1; i++)
#define rreps(i,x) for(ll i = (ll)(x); 1 <= i; i--)
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const int n_max = 1e5+10;

int main(){
    ll n; cin >> n;
    cout << (n + 1) / 2 << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
long long int dp[1000050][4]={};
long long int N,mod=1000000007;

int main(){
  
    cin>>N;
    dp[0][0]=1;
  	//dp[i][0]=i番目までに0も9もでてこない場合の通り数
  	//dp[i][1]=i番目までに0のみでている場合の通り数
    //dp[i][2]=i番目までに9のみでている場合の通り数
    //dp[i][3]=i番目までに0も9もでている場合の通り数
  	for(long long int i = 1; i <= N; i++){
      	//0,9を除いた1~8の数を選ぶと状態は0のまま
        dp[i][0]=dp[i-1][0]*8;
      	//0の状態から1を選ぶと状態1へ。1の状態から9を除いた0~8の数を選ぶと状態は1のまま
        dp[i][1]=dp[i-1][0]+dp[i-1][1]*9;
      	//0の状態から9を選ぶと状態2へ。2の状態から0を除いた1~9の数を選ぶと状態は2のまま
        dp[i][2]=dp[i-1][0]+dp[i-1][2]*9;
      	//1の状態から9を選ぶと状態3へ。2の状態から0を選ぶと状態3へ。3の状態なら何を選んでも3の状態のまま
        dp[i][3]=dp[i-1][1]+dp[i-1][2]+dp[i-1][3]*10;
        dp[i][0]%=mod;
        dp[i][1]%=mod;
        dp[i][2]%=mod;
        dp[i][3]%=mod;
        
    }
    cout<<dp[N][3]<<endl;
}



Measured memory_bytes: 34772
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory>
#include<cmath>
#include<algorithm>
#include<vector>
double min_double(double a,double  b){
    if(a<b) return a;
    else return b;
}
void swap(int *x,int *y){
    int tmp;
    tmp=*x;
    *x=*y;  
    *y=tmp;
}
int gcd(int a,int b){
    if(a<b) swap(&a,&b);
    if(b<1) return -1;

    if(a%b==0) return b;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a * b / gcd(a,b);
}

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

    std::vector<int> A(N);
    for(int i=0;i<N;i++) std::cin>>A[i];
    std::vector<int> B(A);

    std::sort(A.begin(),A.end());
    for(int i=0;i<N;i++){
        if(B[i]==A[N-1]) std::cout<<A[N-2]<<std::endl;
        else std::cout<<A[N-1]<<std::endl;
    }
    

    return 0;
}

Measured memory_bytes: 4768
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

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

int main(){
    double n, k; cin >> n >> k;
    vector<double> p(n);
    rep(i, n){
        ll j; cin >> j;
        p[i] = (j + 1) / 2.0;
    }

    vector<double> p_sum(n + 1);
    p_sum[0] = 0;
    _rep(i, 1, n + 1){
        p_sum[i] = p_sum[i - 1] + p[i - 1];
    }

    double ans;
    double ans_max = 0;
    rep(i, n - k + 1){
        ans = p_sum[i + k] - p_sum[i];
        ans_max = max(ans, ans_max);
    }
    cout << setprecision(15) << ans_max << endl;
}

Measured memory_bytes: 3328
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[][][] room=new int[4][3][10];
		for(int t=0; t<n;t++) {
			int b=sc.nextInt();
			int f=sc.nextInt();
			int r=sc.nextInt();
			int v=sc.nextInt();
			room[b-1][f-1][r-1]+=v;
		}

		for(int B=0;B<3;B++) {
			for(int F=0;F<3;F++) {
				for(int R=0;R<10;R++) {
					System.out.print(" "+room[B][F][R]);
				}
				System.out.println();
			}
			for(int x=0;x<20;x++) {
				System.out.print("#");
			}
			System.out.println();
		}
		for(int F=0;F<3;F++) {
			for(int R=0;R<10;R++) {
				System.out.print(" "+room[3][F][R]);
			}
			System.out.println();
		}


	}
}



Measured memory_bytes: 29588
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long n;cin>>n;
    long long tr[5];
    for(int i=0;i<5;i++)cin>>tr[i];
    long long mini=tr[0];
    int id=0;
    for(int i=0;i<5;i++){
        if(mini>tr[i]){
            mini=tr[i];
            id=i;
        }
    }
    long long res=0;
    if(n%mini!=0){
        res = n/mini+1;
    }else{
        res=n/mini;
    }
    res+=4;
    cout<<res<<endl;
}


Measured memory_bytes: 256
N = int(input())
S = [int(input()) for _ in range(N)]
if sum(S)%10 != 0:
  print(sum(S))
else:
  A = sorted(S)
  for i in A:
    if (sum(S)-i)%10 != 0:
      print(sum(S)-i)
      exit()
  print(0)

Measured memory_bytes: 8840
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int n, m; cin >> n >> m;
  vector<int>count(m);
    for(int i = 0;i < m;i++){
      count[i]=0;
    }
  for(int i = 0;i < n;i++){
    int k; cin >> k;
    for(int j = 0;j < k;j++){
      int A; cin >> A;
      count[A-1]++;
    }
  }
  int ans = 0;
  for(int i = 0;i < m;i++){
    if(count[i] == n){
      ans++;
    }
  }
  cout << ans << endl;
}

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

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner kb=new Scanner(System.in);
		int a=kb.nextInt();
		int b=kb.nextInt();
		System.out.printf("%d %d\n", a*b,(a+b)*2);
		kb.close();
	}

}

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

int main(){
    int N;
    cin >> N;
    vector<vector<ll>> head(10, vector<ll>(10, 0));
    for (int i = 1; i <= N; i++) {
        int j = i;
        while (j >= 10) j /= 10;
        head[j][i%10]++;
    }
    ll ans = 0;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            ans += head[i][j]*head[j][i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <inttypes.h>

int main(void)
{
    uint_fast8_t a, b;
    scanf("%" SCNuFAST8 "%" SCNuFAST8, &a, &b);
    printf("%" PRIuFAST8 "\n", (a + b) % 24);
    return 0;
}


Measured memory_bytes: 128
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e5+5;
bool f[55][N];
int n,k;
inline void dfs(int x,int y)
{
	if (x>50||f[x][y])return;
	f[x][y]=1;
	fo(i,0,9)
	{
		int yy=(y*10+i)%n;
		dfs(x+i,yy);
	}
}
int main()
{
	scanf("%d",&n);
	dfs(0,0);
	int ans=0;
	fo(i,1,50)
	{
		if (f[i][0])
		{
			ans=i;
			break;
		}
	}
	printf("%d\n",ans);
	return 0;
}

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

int main() {
	int N;
	cin>>N;
	int a,b;
	int A=0;
	for(int i=0;i<N;i++){
		cin>>a>>b;
		A=A+b-a+1;
		}
		cout<<A<<endl;
	return 0;
}

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

struct Node
{
    int key;
    Node *parent,*left,*right;
};
Node *root,*NIL;

void Insert(int k)
{
    Node *y=NIL;
    Node *x=root;
    Node *z;

    z=(Node*)malloc(sizeof(Node));
    z->key=k;
    z->left=NIL;
    z->right=NIL;

    while(x!=NIL)
    {
        y=x;
        if(z->key<x->key)
        {
            x=x->left;
        }
        else
        {
            x=x->right;
        }
    }
    z->parent=y;
    if(y==NIL)
    {
        root=z;
    }else
    {
        if(z->key<y->key)
        {
            y->left=z;
        }else
        {
            y->right=z;
        }
    }
}
void inorder(Node *u)
{
    if(u==NIL)return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}

void preorder(Node *u)
{
    if(u==NIL)return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}

int main()
{
    int n,i,x;
    string com;

    scanf("%d",&n);

    for(i=0;i<n;i++)
    {
        cin>>com;
        if(com=="insert")
        {
            scanf("%d",&x);
            Insert(x);
        }
        else if(com=="print")
        {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

 	return 0;
}



Measured memory_bytes: 26736
#include <iostream>
#include <vector>

void calc(std::vector<int> &v) {
    int total;
    for (int i = 0; i <= 9; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                for (int l = 0; l <= 9; l++) {
                    total = i + j + k + l;
                    v[total]++;
                }
            }
        }
    }
    return; 
}

int main(void) {
    std::vector<int> v(37, 0);
    calc(v);

    int total;
    while (std::cin >> total) {
        if (total > 36) {
            std::cout << 0 << std::endl;
        } else {
            std::cout << v[total] << std::endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3088
#define LOCAL
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rrep(i, n) for(int i=(n-1); i>=0; --i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
static const int INTINF = (INT_MAX >> 1); // 10^9 + 10^7
static const ll LLINF = (LLONG_MAX >> 1);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << '\t' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define DEBUG(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

vector<int> g[MAX];


class UnionFind{
    public:
        vector<ll> par; // 親
        vector<ll> rank; // 木の深さ
        ll numComponent; // 木の数
        void init(ll n){
            par.resize(n);
            rank.assign(n, 1LL);
            for(ll i=0; i<n; ++i) par[i] = i;
            numComponent = n;
        }

        ll findRoot(ll x){
            if(par[x] == x) return x;
            else return par[x] = findRoot(par[x]);
        }

        void unite(ll x, ll y){
            x = findRoot(x);
            y = findRoot(y);
            if(x == y) return;
            if(rank[x] < rank[y]) swap(x, y);
            rank[x] += rank[y];
            par[y] = x;
            numComponent--;
            return;
        }

        bool same(ll x, ll y){
            return findRoot(x) == findRoot(y);
        }

        ll size(ll x){
            return rank[findRoot(x)];
        }
};


int main(int argc, const char * argv[]) {
  std::cout << std::fixed << std::setprecision(15);

  int N, M; cin >> N >> M;
  rep(i, N){
    int K; cin >> K;
    rep(j, K){
      int l; cin >> l;
      l--;
      g[l].push_back(i);
    }
  }

  UnionFind unionFind;
  unionFind.init(N);

  rep(i, M){
    // DEBUG(i);
    rep(j, g[i].size()){
      // DEBUG(g[i][j]);
      if(j == 0) continue;
      // DEBUG(g[i][j]);
      // DEBUG(g[i][0]);
      unionFind.unite(g[i][j], g[i][0]);
    }
  }

  if(unionFind.size(0) == N){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }

}  


Measured memory_bytes: 5120
n, k = map(int, input().split())
A = list(map(int, input().split()))
counts = [[0, 0] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if A[i] < A[j]:
      if i > j:
        counts[i][0] += 1
      if i < j:
        counts[i][1] += 1

total = 0
for i in range(n):
  total += counts[i][0] * (k * (k + 1) // 2) + counts[i][1] * (k * (k - 1) // 2)
  total %= 1000000007

print(total)

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

#define pb push_back
#define fi first
#define SZ(x) (int((x).size()))
#define se second
#define ll long long
#define pq priority_queue
#define MP make_pair
#define pii pair<int,int>
#define debug(x) cerr<<#x<<"="<<x<<'\n'

const ll mod=1e9+7;
int n,a,b;

ll PoW(ll base,int x) {
	ll res=1;
	while (x) {
		if (x%2==1) res=(res*base)%mod;
		base=(base*base)%mod;
		x/=2;
	}
	return res;
}

ll calc(int x,int y) {
	ll tmp1=1,tmp2=1;
	for (int i=x-y+1;i<=x;i++) (tmp1*=(ll)i)%=mod;
	for (int i=2;i<=y;i++) (tmp2*=(ll)i)%=mod;
	return tmp1*PoW(tmp2,mod-2)%mod;
}

int main(){ 
	cin>>n>>a>>b;
	ll ans=PoW(2,n)-1;
	if (ans<0) ans+=mod;
	(ans+=mod-calc(n,a))%=mod;
	(ans+=mod-calc(n,b))%=mod;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
//#pragma warning disable
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System;
using System.Numerics;
using System.Threading.Tasks;
using static System.Math;
using static System.Console;
class Z { static void Main() => new K(); }
class K
{
	int F() => int.Parse(ReadLine());
	long FL() => long.Parse(ReadLine());
	int[] G() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
	long[] GL() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray();
	public const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var I = G();
		int N = I[0], M = I[1];
		var a = new int[N][];
		for (int i = 0; i < N; i++) a[i] = G().Select(x => x - 1).ToArray();
		var ng = new bool[M];
		var min = N + 1;
		for (var i = 0; i < M; i++)
		{
			var count = new int[M];
			for (int j = 0; j < N; j++)
				for (var k = 0; k < M; k++)
					if (!ng[a[j][k]])
					{
						count[a[j][k]]++;
						break;
					}
			//Console.WriteLine("ng = " + string.Join(", ", closed));
			//Console.WriteLine("c = " + string.Join(", ", count));
			var star = 0;
			for (var j = 0; j < M; j++) if (count[star] < count[j]) star = j;
			min = Min(min, count[star]);
			ng[star] = true;
		}
		WriteLine(min);
	}
}


Measured memory_bytes: 15692
import sys
stdin = sys.stdin

mod = 10**9 + 7

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

N = ni()
ans = 0
for _ in range(N):
    x, u = ns().split()
    if u =="JPY":
        ans += int(x)
    else:
        ans += float(x)*380000
print("{:.6f}".format(ans))
    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
typedef long long ll;

int main(){
    ll n, a, b, c;
    map<char, ll>m;
    cin >> n >> a >> b >> c;

    vector<string>s(n, "");
    REP(i, n) cin >> s[i];

    m['A'] = a;
    m['B'] = b;
    m['C'] = c;

    vector<char> ans;

    if ((a || b || c) == 0){
        cout << "No" << endl;
        return 0;
    }

    string curr, next;
    if (a + b + c == 1){
        REP(i, n){
            curr = s[i];
            if (m[curr[0]] == 0 && m[curr[1]] == 0){
                cout << "No" << endl;
                return 0;
            }
            if (m[curr[0]] == 0) {
                m[curr[0]]++; 
                m[curr[1]]--;
                ans.push_back(curr[0]);
            }
            else {
                m[curr[0]]--; 
                m[curr[1]]++;
                ans.push_back(curr[1]);
            }
        }
        cout << "Yes" << endl;
        REP(j, ans.size()) cout << ans[j] << endl;
        return 0;
    }

    else{
        REP(i, n){
            curr = s[i];
            if (m[curr[0]] == 0 && m[curr[1]] == 0){
                
                cout << "No" << endl;
                REP(j, ans.size()) cout << ans[j] << endl;
                return 0;
            }
            if (m[curr[0]] == 0) {
                m[curr[0]]++; 
                m[curr[1]]--;
                ans.push_back(curr[0]);
            }
            else if (m[curr[1]] == 0) {
                m[curr[0]]--; 
                m[curr[1]]++;
                ans.push_back(curr[1]);
            }
            else{ // both nonzero
                if (i == n - 1) {// either is fine
                    ans.push_back(curr[0]);
                }
                else{
                    next = s[i+1];
                    if (curr[0] == next[0] || curr[0] == next[1]){
                        m[curr[0]]++;
                        m[curr[1]]--;
                        ans.push_back(curr[0]);
                    }
                    else{
                        m[curr[0]]--;
                        m[curr[1]]++;
                        ans.push_back(curr[1]);
                    }
                }
            }
        }
        cout << "Yes" << endl;
        REP(j, ans.size()) cout << ans[j] << endl;
        return 0;
    }
}


Measured memory_bytes: 6756
import bisect, sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(-x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2

#K番目が負
if res1 >= k:
    pl.sort(reverse=True)
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = p * m
        tmp = 0
        for i in range(p):
            while tmp < m and pl[i] * mi[tmp] < x:
                tmp += 1
            cnt -= tmp
        if cnt < k:
            r = x
        else:
            l = x
    print(-l)

#K番目が0
elif res1 + res2 >= k:
    print(0)

#K番目が正
else:
    k = k - res1 - res2
    pl.sort(reverse=True)
    pl2 = pl[::-1]
    mi.sort(reverse=True)
    mi2 = mi[::-1]
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = 0
        tmp = 0
        for i in range(p):
            if pl[i] ** 2 <= x:
                cnt -= 1
            while tmp < p and pl[i] * pl2[tmp] <= x:
                tmp += 1
            cnt += tmp
        tmp = 0
        for i in range(m):
            if mi[i] ** 2 <= x:
                cnt -= 1
            while tmp < m and mi[i] * mi2[tmp] <= x:
                tmp += 1
            cnt += tmp

        cnt //= 2
        if cnt < k:
            l = x
        else:
            r = x
    print(r)

Measured memory_bytes: 90708
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,E = inpl()
Start = 0
Goal = N-1
ans = 0
lines = defaultdict(set)
cost = [[0]*N for i in range(N)]
for i in range(E):
    a,b,c = inpl()
    if c != 0:
        lines[a].add(b)
        cost[a][b] += c
        
def Ford_Fulkerson(s): #sからFord-Fulkerson
    global lines
    global cost
    global ans
    queue = deque()     #BFS用のdeque
    queue.append([s,INF])
    ed = [True]*N    #到達済み
    ed[s] = False
    route = [0 for i in range(N)]   #ルート
    route[s] = -1
    #BFS
    while queue:
        s,flow = queue.pop()
        for t in lines[s]:  #s->t
            if ed[t]:
                flow = min(cost[s][t],flow)  #flow = min(直前のflow,line容量)
                route[t] = s
                queue.append([t,flow])
                ed[t] = False
                if t == Goal: #ゴール到達
                    ans += flow
                    break
        else:
            continue
        break
    else:
        return False
    #ラインの更新
    t = Goal
    s = route[t]
    while s != -1:
        #s->tのコスト減少，ゼロになるなら辺を削除
        cost[s][t] -= flow
        if cost[s][t] == 0:
            lines[s].remove(t)
        #t->s(逆順)のコスト増加，元がゼロなら辺を作成
        if cost[t][s] == 0:
            lines[t].add(s)
        cost[t][s] += flow
        t = s
        s = route[t]
        
    return True

while True:
    if Ford_Fulkerson(Start):
        continue
    else:
        break
        
print(ans)


Measured memory_bytes: 7544
// AOJ 2417: Flick Input
// 2017.11.16 bal4u@uu

#include <stdio.h>

char si[] = "wakstnhmyr";
char tr['z'];
char buf[1002];

int main()
{
	int i;
	char *p;

	tr['T'] = 'a', tr['L'] = 'i', tr['U'] = 'u', tr['R'] = 'e', tr['D'] = 'o';
	for (i = 0; si[i]; i++) tr['0'+i] = si[i];

	scanf("%s", p=buf);
	while (*p) {
		if (*p == '0' && *(p+1) == 'U') putchar('n'), putchar('n'), p++;
		else if (*p == '1') p++, putchar(tr[*p]);
		else putchar(tr[*p++]), putchar(tr[*p]);
		p++;
	}
	putchar('\n');
	return 0;
}

Measured memory_bytes: 1792
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n,k=LI()
ans=0
if k==0:
    print(n*n)
    exit()
for b in range(k+1,n+1):
    ans+=n//b*(b-k)+max(0,n%b-k+1)

print(ans)

Measured memory_bytes: 82972
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int W = sc.nextInt();
        long[][] dp = new long[N+1][W+1];
        Sack[] s = new Sack[N];
        for(int i = 0 ; i < N ; i++)
            s[i] = new Sack(sc.nextInt(),sc.nextInt());
        Arrays.sort(s);
        for(int i = 1 ; i <= N ; i++)
        {
            for(int j = 1; j <= W ; j++)
            {
                if(s[i-1].w <= j )
                {
                    dp[i][j] = Math.max(s[i-1].b+dp[i-1][j-s[i-1].w],dp[i-1][j]);
                }else
                {
                    dp[i][j] = dp[i-1][j];
                }
            }

        }
        System.out.println(dp[N][W]);
    }
    static class Sack implements Comparable<Sack>{
        int w,b;
        @Override
        public int compareTo(Sack o) {
            if(w == o.w)
                return 0;
            return w>o.w?1:-1;
        }

        public Sack(int w , int b)
        {
            this.w = w;
            this.b = b;
        }

        @Override
        public String toString() {
            return w+" "+b;
        }
    }
}


Measured memory_bytes: 126164
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int c = stdIn.nextInt();
		int d = stdIn.nextInt();
		int e = stdIn.nextInt();
		int k = stdIn.nextInt();
		
		if(e-a > k) {
			System.out.println(":(");
		}else {
			System.out.println("Yay!");
		}
		
		
		
	}

}


Measured memory_bytes: 22100
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  int count = 0;
  
  for (int i = 0; i < n; i++) {
    cin >> vec[i];
    vec[i]--;
  }

  int next = 0;
  while(1){
      if(next == 1){
        cout << count << endl;
      	break;
      }
      if(count > n) {
        cout << -1 << endl;
        break;
      }
      next = vec[next];
      count++;
    }
}


Measured memory_bytes: 640
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int main(void)
{
	char a[4];
	string op[3];
	cin >> a[0] >> a[1] >> a[2] >> a[3];
	for (int i = 0; i < (1 << 3);i++)
	{
		int ans = a[0] - '0';
		for (int j = 0; j < 3; j++)
		{
			if (i & 1 << j)
			{
				ans += a[j + 1] - '0';
				op[j] = '+';
			}
			else
			{
				ans -= a[j + 1] - '0';
				op[j] = '-';
			}
		}
		if (ans == 7) { break; }
	}
	cout << a[0] << op[0] << a[1] << op[1] << a[2] << op[2] << a[3] << "=7" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=((ll)n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=((ll)a);i<((ll)n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    vl a(n);cin>>a;
    map<ll,ll> b,c;
    rep(i,n){
        b[i+a[i]]++;
        c[i-a[i]]++;
        // b[i]=i+a[i];
        // c[i]=i-a[i];
    }
    ll ans=0;
    for(auto&p:b){
        ll v,cnt;
        tie(v,cnt)=p;
        if(c.find(v)!=c.end())ans += cnt*c[v];
    }
    puta(ans);

    return 0;
}

Measured memory_bytes: 27928
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


n, m = map(int, input().split())
p_list = list(map(int, input().split()))
q_list = list(map(lambda x: x - 1, p_list))

uni = UnionFind(n)

for i in range(m):
    x, y = map(int, input().split())
    uni.union(x-1, y-1)

ret = 0

tmp_dict = dict()

for i in range(n):
    parent = uni.find(i)
    if parent in tmp_dict:
        tmp_dict[parent].append(i)
    else:
        tmp_dict[parent] = [i]

for item in tmp_dict:
    t_list = tmp_dict[item]
    tmp = set()
    for var in t_list:
        tmp.add(q_list[var])
    ret += len(tmp & set(t_list))

print(ret)


Measured memory_bytes: 109420
#include<bits/stdc++.h>
using namespace std;
int n,m,vis[100005],s=0;
vector<int>g[100005];
void dfs(int x,int nw)
{
	vis[x]=nw;
	s+=nw;
	for(int i=0;i<g[x].size();i++)
	{
		if(vis[g[x][i]]==nw)
		{
			long long t=n;
			t=t*(n-1)/2;
			printf("%lld\n",t-m);
			exit(0);
		}
		else if(vis[g[x][i]]==-1)dfs(g[x][i],nw^1);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)vis[i]=-1;
	dfs(1,0);
	printf("%lld\n",s*(n-s)-m);
	return 0;
} 

Measured memory_bytes: 6528
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__

def pi(s):
    p = [0] * len(s)
    for i in range(1, len(s)):
        g = p[i - 1]
        while g and (s[i] != s[g]):
            g = p[g - 1]
        p[i] = g + int(s[i] == s[g])

    return p


def match(s, pat):
    res = []
    p = pi(pat + '\0' + s)
    for i in range(len(p) - len(s), len(p)):
        if p[i] == len(pat):
            res.append(i - 2 * len(pat))

    return res


def main():
    s = input()
    t = input()

    if len(s) < len(t):
        s *= (len(t) + len(s) - 1) // len(s)
    n = len(s)
    s *= 3

    lo, hi = 0, (len(s) + len(t) - 1) // len(t)
    while lo < hi:
        mi = (lo + hi) // 2
        u = mi * t
        if not match(s, u):
            hi = mi
        else:
            lo = mi + 1

    if len(t * (lo - 1)) >= 2 * n:
        print(-1)
        return

    print(lo - 1)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()


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

int main() {
    string s;
    cin >> s;
    int64_t n = s.size();
    vector<int64_t> t(n);
    for (int64_t i = 0; i < n; i++) t[n-i-1] = s[i] - '0';
    int64_t ans = 0;
    for (int64_t b = 0; b < 1 << (n-1); b++) {
        ans += t[0];
        int64_t d = 1;
        for (int64_t i = 0; i < n-1; i++) {
            d = ((b >> i) & 1 ? d*10 : 1);
            ans += t[i+1] * d;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#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 cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define mi          map<int,int>
#define mii         map<pi,int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846

 const int N=1e3+5;

 int mod= 1e9+7;
 int dx[4]={0,0,+1,-1};
 int dy[4]={+1,-1,0,0};  
 
 
int po(int a, int b) {
	a %= mod;
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res * a) % mod;
		a =(a*a) % mod;
		b >>= 1;
	}
	 return res;	
  }
   


void solve() {
   int n,x,t;
   cin>>n>>x>>t;
   if(x>=n) cout<<t<<endl;
   else {
	      int sum=t,cnt=x;
	      while(cnt<n) {
			     sum+=t;
			     cnt+=x;
			  }
			  //~ cout<<cnt<<endl;
			  cout<<sum<<endl;     	      
	   }
	               
}

    
int32_t main() {
	cool;
	int t=1;	

	//cin>>t;
	while(t--)
	  solve();

  return 0;	   
}



Measured memory_bytes: 3616
#include <iomanip>
#include<iostream>
using namespace std;
int main()
{
	double pi = 3.141592653589;
	double r;
	cin >> r;
	cout << fixed << setprecision(6) << pi * r * r << " " << 2 * pi * r << endl;
	cin >> r;
	return 0;
}


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


void dfs(vector<vector<int>> &edges, vector<int> &a, int v, int parent,vector<int> &res, vector<int> &seq) {
  if (seq.empty() || a[v] > seq.back()) {
    seq.push_back(a[v]);
    for (int u : edges[v]) {
      if (u != parent) {
        dfs(edges, a, u, v, res, seq);
      }
    } 
    res[v] = seq.size();
    seq.pop_back();
  } else {
    int lb = lower_bound(seq.begin(), seq.end(), a[v]) - seq.begin();
    int tmp = seq[lb];
    seq[lb] = a[v];
    for (int u : edges[v]) {
      if (u != parent) {
        dfs(edges, a, u, v, res, seq);
      }
    }
    res[v] = seq.size();
    seq[lb] = tmp;
  }
  return;
}
int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  vector<vector<int>> edges(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    edges[u - 1].push_back(v - 1);
    edges[v - 1].push_back(u - 1);
  }
  vector<int> res(N);
  vector<int> seq;
  dfs(edges, a, 0, -1, res, seq);
  for (int i = 0; i < N; i++)
    cout << res[i] << endl;
  return 0;
}

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

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    int maxX = x;
    int minY = y;
    int xx, yy;
    for (int i = 0; i < n; i++) {
        cin >> xx;
        maxX = max(maxX, xx);
    }
    for (int i = 0; i < m; i++) {
        cin >> yy;
        minY = min(minY, yy);
    }
    if (maxX < minY) {
        cout << "No War" << endl;
    } else {
        cout << "War" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
map <string,int> m;
int main()
{ cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin>>n;
  for(int i=1;i<=n;i++)
  { cin>>s;
    m[s]++;
  }
  cout<<"AC x "<<m["AC"]<<'\n';
  cout<<"WA x "<<m["WA"]<<'\n';
  cout<<"TLE x "<<m["TLE"]<<'\n';
  cout<<"RE x "<<m["RE"]<<'\n';
  return 0;
}


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

// {{{
#define PI pair<int, int>
#define mk make_pair
#define reg register
#define ll long long
#define rep(i, Fir, Sec) for(reg int i = Fir; i <= Sec; ++i)
#define per(i, Fir, Sec) for(reg int i = Fir; i >= Sec; --i)
// }}}

using namespace std;

inline int min(reg int Fir, reg int Sec) { return Fir < Sec ? Fir : Sec; }
inline int max(reg int Fir, reg int Sec) { return Fir > Sec ? Fir : Sec; }
inline int read() {
  reg int s = 0; reg char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
  return s;
}

const int maxn = 1e5 + 5;

int n, Fir[maxn], Sec[maxn];
int Cnt1, Cnt2;

int main() {
  //freopen("Fir.in", "r", stdin);
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    int Getin;
    scanf("%d", &Getin);
    if(Getin >= 0) Fir[++Cnt1] = Getin;
    else Sec[++Cnt2] = Getin;
  }
  sort(Fir + 1, Fir + Cnt1 + 1);
  sort(Sec + 1, Sec + Cnt2 + 1);
  if(!Cnt1) {
    int tmp = Sec[Cnt2];
    for(int i = 1; i < Cnt2; i++) tmp -= Sec[i];
    printf("%d\n", tmp);
    for(int i = 1; i < Cnt2; i++) {
      printf("%d %d\n", Sec[Cnt2], Sec[i]);
      Sec[Cnt2] -= Sec[i];
    }
  } else if(!Cnt2) {
    int tmp = Fir[1];
    for(int i = 3; i <= Cnt1; i++) tmp -= Fir[i];
    tmp = Fir[2] - tmp; printf("%d\n", tmp);
    for(int i = 3; i <= Cnt1; i++) {
      printf("%d %d\n", Fir[1], Fir[i]);
      Fir[1] -= Fir[i];
    } printf("%d %d\n", Fir[2], Fir[1]);
  } else {
    int ans = 0;
    for(int i = 1; i <= Cnt1; i++) ans += Fir[i];
    for(int i = 1; i <= Cnt2; i++) ans -= Sec[i];
    printf("%d\n", ans);
    for(int i = 1; i < Cnt1; i++) {
      printf("%d %d\n", Sec[1], Fir[i]);
      Sec[1] -= Fir[i];
    }
    for(int i = 1; i <= Cnt2; i++) {
      printf("%d %d\n", Fir[Cnt1], Sec[i]);
      Fir[Cnt1] -= Sec[i];
    }
  }
  return 0;
}



/*******************************************
  _________________________________________
  < COWSAY.cpp is created by zrz who is weak >
  -----------------------------------------
  \   ^__^
  \  (oo)\_______
  (__)\       )\/\
  ||----w |
  ||     ||
 ********************************************/

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

int R, G, B, N;
int nr, ng;
long long ans = 0;

int main() {
    cin >> R >> G >> B >> N;
    nr = (N + R - 1) / R;
    for (int r=0; r<=nr; ++r) {
        ng = (N-R*r+G-1)/G;
        for (int g=0; g<=ng; ++g) {
            if ((N-R*r-G*g) >= 0 && (N-R*r-G*g) % B == 0) ++ans;
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256