akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::*;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    return ret;
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.is_err() || res.ok().unwrap() == 0 || u8b[0] <= ' ' as u8 {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = std::string::String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}
fn parse<T: std::str::FromStr>(s: &str) -> T { s.parse::<T>().ok().unwrap() }

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { parse(&get_word()) }

#[allow(dead_code)]
macro_rules! d {
    ($e:expr) => {
        {
            let a = $e;
            println!("{} = {:?}", stringify!($e), a);
            a
        }
    }
}

#[allow(dead_code)]
macro_rules! tee {
    ($e:expr) => {
        {
            let a = $e;
            println!("{:?}", a);
            a
        }
    }
}

fn permute(mut a: Vec<u64>) -> Option<Vec<u64>> {
    if a.len() == 1 {
        Some(a)
    } else {
        let odds: Vec<_> = (0..a.len()).filter(|x| a[*x] % 2 == 1).collect();

        match odds.len() {
            0 => Some(a),
            1 => {
                let i = odds[0];
                a.swap(0, i);
                Some(a)
            },
            2 => {
                let i = odds[0];
                let j = odds[1];
                let end = a.len() - 1;
                a.swap(0, i);
                a.swap(j, end);
                Some(a)
            }
            _ => None
        }
    }
}

fn getb(a: &Vec<u64>) -> Vec<u64> {
    let mut b = Vec::new();

    if a.len() == 1 {
        b.push(1);
        b.push(a[0] - 1);
    } else {
        if a[0] % 2 == 1 {
            b.push(a[0] + 1);
        } else {
            b.push(1);
            b.push(a[0]);
        }

        for i in 1..a.len()-1 {
            b.push(a[i]);
        }

        b.push(a[a.len() - 1] - 1);
    }

    b.into_iter().filter(|x| *x != 0).collect()
}

fn main() {
    let n: u64 = get();
    let m: usize = get();
    let a: Vec<u64> = (0..m).map(|_| get()).collect();

    if let Some(a) = permute(a) {
        let b = getb(&a);
        for x in &a {
            print!("{} ", x);
        }
        println!("");
        println!("{}", b.len());
        for x in &b {
            print!("{} ", x);
        }
        println!("");
    } else {
        println!("Impossible");
    }
}


Measured memory_bytes: 380
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <bitset>
#include <queue>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

#define rep(i, n) for(int i = 0;i < n;i++)
const int INF = 1LL << 30;
const int MOD = 1000000007;

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

    int n; cin >> n;
    std::vector<int> a(n); rep(i,n) cin >> a[i];

    int cnt = 0;
    int cur = 1;

    rep(i,n){
        if(a[i]==cur){
            cur++;
            cnt++;
        }
    }
    if(cnt == 0) cout << -1 << endl;
    else cout << n-cnt << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <set>
#include <map>

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define for_p(i, a, b) for(int i = a; i < b; i++)
#define for_m(i, a, b) for(int i = a - 1; i >= b; i--)

//a = s1.size();
//vector<string> s1;
//string s2 = accumulate( s1.begin(), s1.end(), string() );

using namespace std;

int main()
{
  int a = 0 , b = 0, c = 0, d = 0, e = 0, f = 0;
  int i = 0, j = 0;
  double d1 = 0, d2 = 0, d3 = 0, d4 = 0, d5 = 0, d6 = 0;
  int a1[256], a2[512], a3[1024];
  char s1[200000], s2[200000], s3[200000];
  string x, y, z;
  
  cin >> x;
  
  if(x == "Sunny"){
    cout << "Cloudy" << endl;
  }
  if(x == "Cloudy"){
    cout << "Rainy" << endl;
  }
  if(x == "Rainy"){
    cout << "Sunny" <<endl;
  }
}
  



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

using namespace std;

constexpr int M = 2e5 + 10;
constexpr int N = 8000 + 10;
constexpr int O = 4010;
constexpr int MOD = 1e9 + 7;

long long n, a[M], b[M], dp[O][O], fact[N], ans;

long long mypow (long long a, long long b) {
    return b ? (mypow (a * a % MOD, b >> 1) * (b & 1 ? a : 1)) % MOD : 1;
}

long long ch (long long a, long long b) {
    return (fact[a] * mypow (fact[b] * fact[a - b] % MOD, MOD - 2)) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        dp[a[i] + 2000][b[i] + 2000]++;
    }
    fact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = (fact[i - 1] * i) % MOD;
    for (int i = 4000; ~i; i--)
        for (int j = 4000; ~j; j--)
            dp[i][j] = (dp[i][j] + dp[i + 1][j] + dp[i][j + 1]) % MOD;
    for (int i = 0; i < n; i++)
        ans = (ans + dp[2000 - a[i]][2000 - b[i]]) % MOD;
    for (int i = 0; i < n; i++)
        ans = (ans - ch(a[i] * 2 + b[i] * 2, a[i] * 2)) % MOD;
    ans = ((ans %  MOD) + MOD) % MOD;
    ans *= mypow (2, MOD - 2);
    ans %= MOD;
    cout << ans << '\n';
    return 0;
}


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

int main() {
  string s; cin >> s;
  
  if (s == "Sunny") cout << "Cloudy" << endl;
  else if (s == "Cloudy") cout << "Rainy" << endl;
  else if (s == "Rainy") cout << "Sunny" << endl;
  
  return 0;
}

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

int main()
{

  
  ll n,i;
  ll l,r,d;
  cin>>l>>r>>d;
  ll ans=0;
  for(i=l; i<=r; i++)
  {
    if(i%d==0)
      ans++;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3592
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define PI acos(-1)
#define Mod (int)1000000007
#define INFTY (int)INT_MAX
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define All(vec) vec.begin(), vec.end()
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())
#define Count(vec, x) count(vec.begin(), vec.end(), x)
#define Next_permutation(vec) next_permutation(vec.begin(), vec.end())
#define Find(S, s) S.find(s) != string::npos

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    Rep(i, N) cin >> A[i];
    for (int i = 0; i < N - K; i++) {
        if (A[i] < A[K + i]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 4048
while True:
    n = int(input())
    if n == 0:
        break
    oturi = 1000 - n
    li = [500,100,50,10,5,1]
    cnt = [0,0,0,0,0,0]
    for i in range(len(li)):
        cnt[i] = oturi//li[i]
        oturi -= cnt[i]*li[i]
    ans = 0
    for i in range(len(cnt)):
        ans += cnt[i]
    print(ans)


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}


int n;

main(){
  cin>>n;
  vector<int> a(n);
  int res=0;
  rep(i,n){
    cin>>a[i];
    if(a[i]>=n) res++;
  }

  int ans=0;
  while(res>0){
    sort(all(a));
    reverse(all(a));
    int b=a[0]%n;
    int r=(a[0]-b)/n;
    a[0]=b;
    ans+=r;
    FOR(i,1,n){
      a[i]+=r;
    }
    res=0;
    rep(i,n){
      if(a[i]>=n) res++;
    }
  }

  cout<<ans<<endl;

}


Measured memory_bytes: 764
#define DEBUG 0

/**
 * File    : D2.cpp
 * Author  : Kazune Takahashi
 * Created : 2019-5-28 18:47:58
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <random>
#include <chrono>
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef long long ll;

/*
void Yes()
{
  cout << "Yes" << endl;
  exit(0);
}

void No()
{
  cout << "No" << endl;
  exit(0);
}
*/

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

const ll infty = 100000000000007;
int N;
ll A, B;
int p[5010];
ll DP[5010][5010];

int main()
{
  cin >> N >> A >> B;
  for (auto i = 1; i <= N; i++)
  {
    cin >> p[i];
  }
  fill(&DP[0][0], &DP[0][0] + 5010 * 5010, infty);
  DP[0][0] = 0;
  for (auto i = 0; i <= N; i++)
  {
    for (auto j = 0; j <= N; j++)
    {
      if (j < N)
      {
        DP[i][j + 1] = min(DP[i][j + 1], DP[i][j]);
      }
      if (i < N)
      {
        if (p[i + 1] <= j)
        {
          DP[i + 1][j] = min(DP[i + 1][j], DP[i][j] + B);
        }
        else
        {
          DP[i + 1][j] = min(DP[i + 1][j], DP[i][j] + A);
        }
      }
      if (i < N && j < N && p[i + 1] == j + 1)
      {
        DP[i + 1][j + 1] = min(DP[i + 1][j + 1], DP[i][j]);
      }
    }
  }
  cout << DP[N][N] << endl;
}

Measured memory_bytes: 196480
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=300050;
int sum[maxn<<3],lazy[maxn<<3],l[maxn],r[maxn];
int n,M;
vector<int>q[maxn];
inline void push_down(int ID,int l,int r){
	int m=(l+r)>>1;
	sum[ID<<1]+=(m-l+1)*lazy[ID],sum[ID<<1|1]+=(r-m)*lazy[ID];
	lazy[ID<<1]+=lazy[ID],lazy[ID<<1|1]+=lazy[ID],lazy[ID]=0;
}
inline void ins(int ID,int l,int r,int L,int R){
	if(lazy[ID])push_down(ID,l,r);
	if(l>=L&&r<=R){
		sum[ID]+=(r-l+1);
		lazy[ID]++;
		return;
	}
	int m=(l+r)>>1;
	if(m>=L)ins(ID<<1,l,m,L,R);
	if(m<R)ins(ID<<1|1,m+1,r,L,R);
	sum[ID]=sum[ID<<1]+sum[ID<<1|1];
}
inline int query(int ID,int x,int l,int r){
	if(lazy[ID])push_down(ID,l,r);
	if(sum[ID]==0)return 0;
	if(l==r)return sum[ID];
	int m=(l+r)>>1;
	if(m>=x)return query(ID<<1,x,l,m);
	else return query(ID<<1|1,x,m+1,r);
}
int main(){
	scanf("%d%d",&n,&M);
	for(register int i=1;i<=n;i++){
		scanf("%d%d",&l[i],&r[i]);
		q[r[i]-l[i]+1].push_back(i);
	}
	int remain=n;
	for(register int i=1;i<=M;i++){
		int ans=remain;
		remain-=q[i].size();
		if(i!=1)
		for(register int j=1;j*i<=M;j++)ans+=query(1,i*j,1,300000);
		for(register int j=0;j<q[i].size();j++)ins(1,1,300000,l[q[i][j]],r[q[i][j]]);
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 26496
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll n,d;

int main(void){
	scanf("%lld%lld",&n,&d);
	if(d==1){
		printf("%lld\n",n*(n-1)/2LL);
		return 0;
	}
	if(d==n-1){
		printf("%lld\n",n-1LL);
		return 0;
	}
	ll res=(n-d+1)*(n-d)/2LL;
	res--;
	res+=n-1LL;
	printf("%lld\n",res);
	return 0;
}

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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1e9+7;


int main(){
	ios_base::sync_with_stdio(false);
	ll N, W, ans=0;
	ll w[105], v[105];

	cin >> N >> W;
	rep(i,N) cin >> w[i] >> v[i];

	ll w1 = w[0];
	ll dp[105][505] = {};
	rep(i,N) rrep(n,N) rep(j,500){
		if( j + w[i] - w1 < 500 )
			chmax(dp[n+1][j+w[i]-w1], dp[n][j] + v[i]);
	}
	rep(n,N+1) rep(j,500) if( w1*n + j <= W ) chmax(ans, dp[n][j]);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main(void){
    int n;
    cin >> n;
    VI a(n);
    REP(i,n) a[i] = in();
    sort(ALL(a));
    reverse(ALL(a));
    ll ans = 0;
    REP(i,n-1){
        ans += a[(i + 1) / 2];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3984
/**
 *    author:  FromDihPout
 *    created: 2020-07-26
**/

#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    long long n, k;
    cin >> n >> k;
    vector<pair<int,int>> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    sort(a.begin(), a.end());
    
    long long added = 0;
    for (int i = 0; i < n; i++) {
        added += a[i].second;
        if (added >= k) {
            cout << a[i].first << '\n';
            break;
        }
    }
    return 0;
}

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

int A[100000];

int partition(int p, int r) {
	int x = A[r];
	int i = p- 1;
	for (int j = p; j < r; j++) {
		if (A[j] <= x) {
			i++;
			swap(A[i], A[j]);
		}
	}
	swap(A[i + 1], A[r]);
	return i + 1;
}

int main(void) {
	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	int q = partition(0, n - 1);
	for (int i = 0; i < n; i++) {
		if (i == q) cout << "[";
		cout << A[i];
		if (i == q) cout << "]";
		if (i != n - 1) cout << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1548
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int MaxN = 1e5;

int main()
{
	int a,b,c;
	char s[105],t[105],e,f;
	scanf("%s",&s);
	scanf("%s",&t);
	a = strlen(s);
	b = strlen(t);
	if(a < b) c = a;
	else c = b;
	sort(s,s + a);
	sort(t,t + b,greater<char>());
	for(int i = 0;i < c;i++)
	{
		if(s[i] < t[i]) 
		{
			printf("Yes\n");
			return 0;
		}
		if(s[i] > t[i])
		{
			printf("No\n");
			return 0;
		}
	}
	if(a < b) printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vpi = vector<pii>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpl = vector<pll>;
using vs = vector<string>;

int main()
{
    int n;
    cin >> n;
    vi xs(n);
    for(int i=0; i<n; i++) cin >> xs.at(i);

    int ans = static_cast<int>(1e6);
    for(int i=1; i<=100; i++)
    {
        int sun = 0;
        for(auto x : xs)
        {
            sun += (x - i) * (x - i);
        }
        if(sun < ans) ans = sun;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int min=Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for(int i=0;i<n;i++){
            x[i]=sc.nextInt();
            min = Math.min(min,x[i]);
            max = Math.max(max,x[i]);
        }

        int mincost = Integer.MAX_VALUE;
        for(int i=min;i<max+1;i++){
            int sum=0;
            for(int j=0;j<n;j++){
                sum+=Math.pow(i-x[j],2);
            }
            mincost=Math.min(mincost,sum);
        }
        System.out.println(mincost);


    }

}

Measured memory_bytes: 23764
#include <iostream>
#include <cmath>
 
int main() {
  int a,b,c,k;
  std::cin >> a;
  std::cin >> b;
  std::cin >> c;
  std::cin >> k;

  int max = a < b ? (b < c ? c : b) : (a < c ? c : a);
 
  std::cout << std::pow(2, k)*max + a + b + c - max << std::endl;
}

Measured memory_bytes: 256
#include <iostream>

const int N = 1000;

int main() {
    using namespace std;
    int l[N], r[N], n;

    cin >> n;

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

    int sum = 0;
    for (i=0; i<n; ++i) {
        sum += r[i] - l[i] + 1;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
from enum import Enum


class DFS():
    class Color(Enum):
        WHITE = 0
        GRAY = 1
        BLACK = 2

    def __init__(self, M, n):
        self.M = M
        self.n = n
        self.color = [self.Color.WHITE for _ in range(self.n)]
        self.d, self.f = [-1] * self.n, [-1] * self.n
        self.tt = 0
        self.nt = [0] * self.n

    def next(self, u: int):
        while self.nt[u] < self.n:
            v = self.nt[u]
            self.nt[u] = v + 1
            if self.M[u][v] != 0:
                return v
        return -1

    def dfs_visit(self, r: int):
        S = []                  # list をスタックとして使う
        S.append(r)
        self.color[r] = self.Color.GRAY
        self.tt += 1
        self.d[r] = self.tt
        while len(S) > 0:
            # スタックの一番上（= listの末尾）の値を取得 ※ pop()するとlistからなくなるので[-1]でアクセス
            u = S[-1]
            v = self.next(u)
            if v != -1:
                if self.color[v] == self.Color.WHITE:
                    self.color[v] = self.Color.GRAY
                    self.tt += 1
                    self.d[v] = self.tt
                    S.append(v)
            else:
                S.pop()
                self.color[u] = self.Color.BLACK
                self.tt += 1
                self.f[u] = self.tt

    def dfs(self):
        for u in range(self.n):
            if self.color[u] == self.Color.WHITE:
                self.dfs_visit(u)

        for i in range(self.n):
            print(f'{i+1} {self.d[i]} {self.f[i]}')


def main():
    n = int(input())
    M = [[0] * n for _ in range(n)]

    for i in range(n):
        line = input()
        inputs = [int(x) for x in line.split(' ')]
        u = inputs.pop(0)
        u -= 1                  # 0 オリジンへ変換
        _ = inputs.pop(0)       # k （使わない...）
        for v in inputs:
            v -= 1              # 0 オリジンへ変換
            M[u][v] = 1

    DFS(M, n).dfs()


if __name__ == '__main__':
    main()



Measured memory_bytes: 6408
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] temoti = new int[N];
		for (int i = 0; i < N; i++) {
			temoti[i] = scan.nextInt();
		}
		insertionSort(temoti, N);
	}

	public static void insertionSort(int[] A, int N) {
		for (int i = 0; i < N; i++) {
			int v = A[i]; // 1枚取り出す
			int j = i - 1;
			while (j >= 0 && A[j] > v) {// 取り出した一枚より前の方に持っていたカードと比較
				A[j + 1] = A[j];
				j--;
			}
			A[j + 1] = v;
			for (int k = 0; k < N; k++) {
				if (k == N - 1) {
					System.out.print(A[k]);
				} else {
					System.out.print(A[k] + " ");
				}
			}
			System.out.println("");
		}

	}
}



Measured memory_bytes: 32000
using System;

class B{
  static void Main(){
    int N = int.Parse(Console.ReadLine()), ans = 0;
    char[] A = Console.ReadLine().ToCharArray();
    char[] B = Console.ReadLine().ToCharArray();
    char[] C = Console.ReadLine().ToCharArray();
    for (int i = 0; i < N; i++){
      if (A[i] == B[i]) {
        if (A[i] != C[i]) ans += 1;
        else ;
      }
      else if (B[i] == C[i]) {
        if (B[i] != A[i]) ans += 1;
        else ;
      }
      else if (A[i] == C[i]) {
        if (B[i] != C[i]) ans += 1;
        else ;
      }
      else ans += 2;
    }
    Console.WriteLine(ans);
  }
}

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


int main()
{
 	int x,a,b;
    cin>>x>>a>>b;
    
  	int one=x-a;
  	int two=x-b;
  
  	if(abs(one)>abs(two)) cout<<"B"<<endl;
  	else cout<<"A"<<endl;
  
  
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int c[12][12];
int a[220][220];
ll dp[12][12];

void solve() {
	rep(i, 12)rep(j, 12) dp[i][j] = INF;
	rep(i, 10)rep(j, 10) {
		if(c[i][j] == -1) continue;
		dp[i][j] = c[i][j];
	}

	rep(k, 10)rep(i, 10)rep(j, 10) {
		dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	}
}
int main(void) {
	int h, w; cin >> h >> w;
	rep(i, 10)rep(j, 10) cin >> c[i][j];
	rep(i, h)rep(j, w) cin >> a[i][j];
	solve();
	ll sum = 0;
	rep(i, h)rep(j, w) {
		if(a[i][j] == -1) continue;
		// printf("%d %lld\n", a[i][j], dp[a[i][j]][1]);
		sum += dp[a[i][j]][1];
	}
	printf("%lld\n", sum);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

//find_by_order gives kth-largest element
//order_of_key gives the number of items in the set that are strictly smaller!!

// OT.find_by_order(k-1)
// 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define db4(x, y, z, w) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << "," << #w << "=" << w << endl
#define ll long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define X first
#define Y second
#define sz(x) (int)((x).size())
#define pii pair<int,int>
#define MOD (ll)(998244353)
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
typedef vector<int> vi;
#define inf (ll)(1e18)
#define double long double
#define int long long

//////////////////////
const int N = 100005;


int32_t main() {

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

    char c;
    cin >> c;
    if(c == 'A') cout << "T\n";
    else if(c == 'T') cout << "A\n";
    else if(c == 'G') cout << "C\n";
    else cout << "G\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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;}
typedef long long ll;

ll n,k;
string s;

int main() {
  cin >> s >> k ;
  int n=s.size();
  if(count(all(s),s[0])==s.size()){
    cout << s.size()*k/2 << endl;
    return 0;
  }
  ll a=0,cnt=0;
  rep(i,s.size()-1){
    cnt=1;
    while(s[i]==s[i+1]) i++,cnt++;
    if(cnt>1) a+=cnt/2;
  }
  if(s[0]!=s[n-1]){
    cout << a*k << endl;
    return 0;
  }
  s+=s;
  ll b=0;
  rep(i,s.size()-1){
    cnt=1;
    while(s[i]==s[i+1]) i++,cnt++;
    if(cnt>1) b+=cnt/2;
  }
  cout << a+(b-a)*(k-1) << endl;
}

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

signed main() {
  int X; cin >> X;
  
  int b = 0; 
  
  while(true) {
    int x = X-(int)(pow(b,5));
    int a = 1;
    while(pow(a,5) < x) {
      a++;
    }
    if(pow(a,5) == x) {
      cout << a << " " << -b << endl;
      return 0;
    }
    x = X+(int)(pow(b,5));
    while(pow(a,5) < x) {
      a++;
    }
    if(pow(a,5) == x) {
      cout << a << " " << b << endl;
      return 0;
    }
    b++;
  }
}

Measured memory_bytes: 4012
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int p[202020];
int c[202020][2];
bool vis[202020];
int rt[202020];
int getr(int x)
{
	if(x==rt[x])
		return x;
	rt[x]=getr(rt[x]);
	return rt[x];
}
double calc(int a,int b)
{
	if(b==0)
		return 1e100;
	else
		return (double)a/b;
}
priority_queue<pair<double,int> > q;
int main()
{
	int n,x,now,pp;
	long long ans=0;
	scanf("%d",&n);
	memset(c,0,sizeof(c));
	for(int i=2;i<=n;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		c[i][x]++;
		if(i!=1)
			q.push(make_pair(calc(c[i][0],c[i][1]),i));
		rt[i]=i;
	}
	memset(vis,0,sizeof(vis));
	while(!q.empty())
	{
		now=q.top().second;
		q.pop();
		if(vis[now])
			continue;
		vis[now]=true;
		pp=getr(p[now]);
		rt[now]=pp;
		ans+=(long long)c[pp][1]*c[now][0];
		c[pp][0]+=c[now][0];
		c[pp][1]+=c[now][1];
		if(pp!=1)
			q.push(make_pair(calc(c[pp][0],c[pp][1]),pp));
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 9328
import heapq

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

h = []
for v in A:
    heapq.heappush(h, -v)

for i in range(M):
    v = heapq.heappop(h)
    # print(v)
    heapq.heappush(h, -(-v // 2))

print(-sum(h))

Measured memory_bytes: 14180
#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++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
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(){
    int a, b, c, d, e; cin >> a >> b >> c >> d >> e;
    int f = a * 60 + b;
    int g = c * 60 + d;
    int ans = g - f - e;
    cout << ans << endl;  
}

Measured memory_bytes: 3636
#include<cstdio>

int main(){
    int l,r,d;
    scanf("%d%d%d",&l,&r,&d);
    int ans = 0;
    for(int i = d; i <= r; i+=d){
        if(i>=l && i<=r) ans++;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 1732
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string S;
    int N,A;
    cin >> N >> S;
    for(int i = 0; i < S.size(); i++){
         A = S[i] - 'A';
         A = (A + N) % 26;
         S[i] = A + 'A';
    }
    cout << S << endl;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use proconio::derive_readable;
use proconio::fastout;
#[allow(unused_imports)]
use num::Integer;
#[allow(unused_imports)]
use itertools::Itertools;

#[fastout]
fn main() {
  input! {
    n: usize,
    a: [Usize1; n-1],
  }
  let mut c = vec![0; n];
  for &x in &a {
    c[x] += 1;
  }
  for &x in &c {
    println!("{}", x);
  }
}


Measured memory_bytes: 5504
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<map>
#include<cstdint>
#include<unordered_map>
//#include<boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < ( int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second


//namespace mp = boost::multiprecision;

//using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

int size(int n) {
	int count = 0;
	while (n > 0) {
		n /= 10;
		count++;
	}
	return count;
}

typedef pair<int, int> P;

bool ps1(const P& element1, const P& element2)
{//first昇順
	return element1.first < element2.first;
}
bool ps2(const P& element1, const P& element2)
{//first降順
	return element1.first > element2.first;
}
bool ps3(const P& element1, const P& element2)
{//second昇順
	return element1.second < element2.second;
}
bool ps4(const P& element1, const P& element2)
{//second降順
	return element1.second > element2.second;
}
int main() {
	ll N;
	scanf("%lld", &N);
	int sizeN = size(N);
	string SFT = "357";
	int i = 21;
	int ans = 0;
	while (i < pow(4, sizeN)) {
		deque<char>a;
		vector<int>count(3);
		int tmp = i;
		bool flag = true;
		while (tmp > 0) {
			rep(j, 3) {
				if (tmp % 4 == j + 1) {
					a.push_front(SFT[j]);
					count[j]++;
				}
				else if (tmp % 4 == 0) {
					flag = false;
					break;
				}
			}
			tmp /= 4;
		}
		if (*min_element(all(count)) > 0&&flag) {
			string s = "";
			rep(j, a.size()) {
				s += a[j];
			}
			ll aa = stoll(s);
			if (aa <= N) {
				ans++;
			}
		}

		i++;
	}
	cout << ans << endl;

}


Measured memory_bytes: 256
use proconio::*;
use proconio::marker::*;

use std::collections::VecDeque;

#[fastout]
#[allow(non_snake_case)]
fn main() {
    input! {
        N: usize, M: usize,
        mut AB: [(Usize1, Usize1); M],
    }
    let mut edges: Vec<Vec<usize>> = vec![vec![]; N];
    for &(A, B) in AB.iter() {
        edges[A].push(B);
        edges[B].push(A);
    }
    let mut q = VecDeque::new();
    q.push_front(0usize);
    let mut numbers = vec![std::usize::MAX; N];
    while q.len() != 0 {
        let room = q.pop_back().unwrap();
        for &each in edges[room].iter() {
            if numbers[each] == std::usize::MAX {
                numbers[each] = room;
                q.push_front(each);
            }
        }
    }
    println!("Yes");
    for &number in numbers[1..].iter() {
        println!("{}", number + 1);
    }
}


Measured memory_bytes: 17288
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
	return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class Program
{
    public static void Main()
    {
	var tmp = ReadIntArray();
	int h = tmp[0], w = tmp[1], a = tmp[2], b = tmp[3];

	    for (int i = 0; i < b; i++)
	    {
		Write(new String('0', a));
		Write(new String('1', w-a));
		WriteLine("");
	    }
	    for (int i = 0; i < h - b; i++)
	    {
		Write(new String('1', a));
		Write(new String('0', w-a));
		WriteLine("");
	    }
    }
}


Measured memory_bytes: 16340
#include <stdio.h>
#include<math.h>
int main(){
  int n,x[102],y[102],i,j,k,D1=0,D4=0;
  double D2=0.0,D3=0.0;
  scanf("%d",&n);
  for(i=0; i<n; i++)scanf("%d",&x[i]);
  for(i=0; i<n; i++)scanf("%d",&y[i]);
  for(i=0; i<n; i++)D1+=abs(x[i]-y[i]);
  for(i=0; i<n; i++)D2+=pow(x[i]-y[i],2);
  D2=pow(D2,(double)1/2);
  for(i=0; i<n; i++)D3+=pow(abs(x[i]-y[i]),3);
  D3=pow(D3,(double)1/3);
  for(i=0; i<n; i++)if(D4<abs(x[i]-y[i]))D4=abs(x[i]-y[i]);
  printf("%lf\n%lf\n%lf\n%lf\n",(float)D1,D2,D3,(float)D4);
  return 0;
}


Measured memory_bytes: 1992
class Integer
  def combination(k)
    return 1 if k.zero?
    (self - k + 1..self).inject(:*) / k.factorial
  end

  def permutation(k)
    return 1 if k.zero?
    (self - k + 1..self).inject(:*)
  end

  def factorial
    return 1 if self.zero?
    (1..self).inject(:*)
  end
end

n, m = gets.split.map(&:to_i)
candies = gets.split.map(&:to_i)
tmp = 0
hash = Hash.new(0)
candies.each_with_index do |c, i|
  mod = (tmp + c) % m
  hash[mod] += 1
  tmp = mod
end
sum = 0
hash.each { |k, v| sum += v.combination(2) }
sum += hash[0]
puts sum


Measured memory_bytes: 14732
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
//const int inf = 1e9 + 7;
//int dy[] = {0, 0, -1, 1};
//int dx[] = {1, -1, 0, 0};
ll calc(ll a) {
    if (a % 2 == 0) {
        if ((a / 2) % 2 == 0) {
            return 0 ^ a;
        } else {
            return 1 ^ a;
        }
    } else {
        if (((a - 1) / 2) % 2 == 0) {
            return 0 ^ (a - 1) ^ a;
        } else {
            return 1 ^ (a - 1) ^ a;
        }
    }
}
int main() {
    ll a, b; cin >> a >> b;
    cout << (calc(a - 1) ^ calc(b)) << endl;
}


Measured memory_bytes: 256
#include<cstdio>

int main(){
  int N;
  scanf("%d", &N);
  int in;
  int m_in = 200000;
  int cn = 0;
  for(;N-->0;){
    scanf("%d", &in);
    if(m_in >= in){
      cn++;
      m_in = in;
    }
  }
  
  printf("%d\n", cn);
  
  return 0;
}

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

ll m,n,a,b;
int main(){
	scanf("%lld%lld%lld%lld",&m,&n,&a,&b);
	if (!(m%a) && !(n%b)){ puts("No"); return 0; }
	ll y=(1000000000ll*(m/a)*(n/b)+1)/(m*n-(m/a)*(n/b));
	if (y>1000000000ll) y=1000000000ll;
	y-=5;if(y<1)y=1;
	for (; ; y++){
		ll x=(y*(m*n-(m/a)*(n/b))-1)/((m/a)*(n/b));
		if (abs(x)>1000000000) break;
		if (x>y*(a*b-1)){
			puts("Yes");
			int i,j;
			for (i=1; i<=m; i++)
				for (j=1; j<=n; j++) printf("%d%c",(!(i%a) && !(j%b))?-x:y,(j<n)?' ':'\n');
			return 0;
		}
	}
	for (y=1; y<=n*m; y++){
		ll x=(y*(m*n-(m/a)*(n/b))-1)/((m/a)*(n/b));
		if (abs(x)>1000000000) break;
		if (x>y*(a*b-1)){
			puts("Yes");
			int i,j;
			for (i=1; i<=m; i++)
				for (j=1; j<=n; j++) printf("%d%c",(!(i%a) && !(j%b))?-x:y,(j<n)?' ':'\n');
			return 0;
		}
	}
	puts("No");
	return 0;
}


Measured memory_bytes: 2816
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 10000000
using namespace std;
typedef pair<int,int> P;
int main(){
    vector<int> allow(100001,0);
    int n;
    cin >> n;
    rep(i,n){
        int a,b;
        cin >> a >> b;
        allow[a-1]++;
        allow[b]--;
    }
    int ans;
    for(int i=0; i<=n; i++){
        if(i) allow[i] += allow[i-1];
        if(allow[i] >= i) ans = i;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3100
#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 gcd(int a, int b) {
    if (a%b==0) {
        return b;
    }
    else {
        return gcd(b, a%b);
    }
}

int lcm(int a, int b) {
    return a*b/gcd(a, b);
}

int main() {
    int k;
    cin >> k;
    int ans = 0;

    for (int a=1; a<=k; ++a) {
        for (int b=1; b<=k; ++b) {
            for (int c=1; c<=k; ++c) {
                ans += gcd(gcd(a, b), c);
            }
        }
    }

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

Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

string s;

int main(void) {
    cin >> s;
    int ans = s.size();
    REP(i, s.size() - 1) {
        if (s[i] != s[i + 1]) {
            chmin(ans, max(i + 1, (int) s.size() - i - 1));
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define elnd endl //* missspell check
const ll INF = 1LL << 60;

void solve(long long N, std::vector<long long> A){
    vector<ll> dp(N);
    fill(dp.begin(), dp.end(), INF);
    ll res;
    for(ll i=0; i< N; i++){
        *upper_bound(dp.begin(), dp.end(), A[i]) = A[i];
    }
    res = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
    cout << res << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
        A[i] = -A[i];
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>//可変長配列
#include<algorithm>//sort,二分探索,など
#include<map>//map(辞書)

using namespace std;

int main(void){
    long int N, K;
    cin >> N >> K;
    if(N > K) N %= K;
    while(abs(N-K) < N){
        N = abs(N-K);
        // cout << N << endl;
    }
    cout << N << endl;
    return 0;
}

Measured memory_bytes: 3580
#include<stdio.h>
int main(void)
{
	int n, cake = 4, donut = 7, flag = 0;
	scanf("%d", &n);

	for (int i = 0; i <= 100 ;i++) {
		for (int j = 0; j <= 100 ; j++) {
			if (n == cake * i + donut * j) {
				flag++;
				break;
			}
			else if(n < cake * i + donut * j){
				break;
			}
		}
		if (n == cake * i) {
			flag++;
			break;
		}
		if (n == donut * i) {
			flag++;
			break;
		}
	}

	if (flag != 0) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}

	return 0;
}



Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf = 0x3f3f3f3f;
const int maxn = 200000 + 10;
map<int, int> pre;
int inline idx(char x)
{
  return x - 'a';
}
char s[maxn];
int n;
int main()
{
  scanf("%s", s);
  n = strlen(s);
  pre[0] = 0;
  int presum = 0;
  for (int i = 0; i < n-1; i++)
  {
    presum ^= (1 << (idx(s[i])));
    if (pre.find(presum) == pre.end())
    {
      pre[presum] = i + 1;
    }
    for (int j = 0; j < 26; j++)
    {
      if (pre.find(presum ^ (1 << j)) != pre.end())
      pre[presum] = min(pre[presum], pre[presum ^ (1 << j)] + 1);
    }
  }
  presum ^= (1 << idx(s[n-1]));
  if (pre.find(presum) == pre.end())
  {
    pre[presum] = n - 1;
  }
  int ans = pre[presum] + 1;
  for (int j = 0; j < 26; j++)
  {
      if (pre.find(presum ^ (1 << j)) != pre.end())
      ans = min(ans, pre[presum ^ (1 << j)] + 1);
  }
  printf("%d\n", ans);

}


Measured memory_bytes: 9856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PI 3.14159265358979
#define EPS 1e-8
#define mod 1000000007
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
	 
const ll INF=(ll)2e18;
		
		
const int N=2e5+5;
		
		
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
				
	ll n;
	cin>>n;
	string s;
	cin>>s;
	
	ll q;
	cin>>q;
	
	while(q)
	{
		q--;
		ll k;
		cin>>k;
		ll ans=0;
		ll c1=0;//"D"
		ll c2=0;//"M"
		ll c3=0;//"DM"
		
		for(ll i=0;i<min(n,k);i++)
		{
			if(s[i]=='D')
			{
				c1++;
			}
			else if(s[i]=='M')
			{
				c2++;
				c3+=c1;
			}
			else if(s[i]=='C')
			{
				ans+=c3;
			}
		}

		for(ll i=k;i<n;i++)
		{
			if(s[i-k]=='D')
			{
				c1--;
				c3-=c2;
			}
			else if(s[i-k]=='M')
			{
				c2--;
			}
			
			
			
			
			if(s[i]=='D')
			{
				c1++;
			}
			else if(s[i]=='M')
			{
				c2++;
				c3+=c1;
			}
			else if(s[i]=='C')
			{
				ans+=c3;
			}
			
		}
		cout<<ans<<endl;
	}			
				
}


Measured memory_bytes: 1948
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
signed main(){
	int n,k;cin >> n >> k;
	vector<int> a(n);
	rep(i,n)cin >> a[i];
	for(int i = k;i < n;i++){
		if(a[i-k] < a[i])cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 4840
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
void chmax(LL& a, LL b) {
	a = max(a, b);
}
//////////////

void solve() {
	LL r, D, X;
	cin >> r >> D >> X;
	for (int i = 1; i <= 10; ++i) {
		X = r * X - D;
		cout << X << endl;
	}
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

/*ここまでテンプレ*/


/*ここからmain関数*/

int main()
{
	long long int A, B;
	cin >> A >> B;

	long long int S[50], T[50];

	//f(0,A-1)の計算
	if (A != 0)
	{
		long long int a = (A - 1) % 4;
		if (a == 0 || a == 3) S[0] = 0;
		if (a == 1 || a == 2) S[0] = 1;
	}
	else
		S[0] = 0;

	long long int now = 2;
	for (int i = 1; i < 50; i++)
	{
		long long int m = (A - 1) % (now * 2);
		if (m < now)
		{
			S[i] = 0;
		}
		else
		{
			if ((m - now + 1) % 2 == 0)
				S[i] = 0;
			else
				S[i] = 1;
		}

		now *= 2;
	}

	//f(0,B)の計算
	long long int a = B % 4;
	if (a == 0 || a == 3) T[0] = 0;
	if (a == 1 || a == 2) T[0] = 1;

	now = 2;
	for (int i = 1; i < 50; i++)
	{
		long long int m = B % (now * 2);
		if (m < now)
		{
			T[i] = 0;
		}
		else
		{
			if ((m - now + 1) % 2 == 0)
				T[i] = 0;
			else
				T[i] = 1;
		}

		now *= 2;
	}

	//XOR
	long long int ans=0;
	now = 1;
	for (int i = 0; i < 50; i++)
	{
		if (S[i] != T[i])
			ans += now;

		now *= 2;
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define f(i,j,k) for(int i=j;i<k;i++)
int main(){
    long long a,b,c,ans=0,aa,bb,cc;
    cin>>a>>b>>c;
    if(a==b&&b==c&&a%2==0){
        cout<<-1<<endl;
        return 0;
    }
    while(a%2==0&&b%2==0&&c%2==0){
        aa=a/2;
        bb=b/2;
        cc=c/2;
        a=bb+cc;
        b=aa+cc;
        c=aa+bb;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int i;
    char str[15],str1[5]="2018";
    while(scanf("%s",str)!=EOF)
    {
        for(i=0;i<4;i++)
        {
            str[i]=str1[i];
        }
        printf("%s\n",str);
    }
    return 0;
}


Measured memory_bytes: 128
using System;
class MinMax {  
  static void Main() {  
    string[] str = Console.ReadLine().Split();
    int s = int.Parse(str[0]);
    int w = int.Parse(str[1]);
    if(w >= s){
        Console.WriteLine("unsafe");
    }else{
        Console.WriteLine("safe");
    } 
   }
 }

Measured memory_bytes: 17696
N=int(input())
A=list(map(int, input().split()))
f=A[0]
g=A[1]
while f%g!=0:
  f,g=[g, f%g]
for i in range(2,N):
  f=A[i]
  while f%g!=0:
    f,g=[g, f%g]
print(g)

Measured memory_bytes: 14252