akhauriyash/Code-Regression huggingface dataset:
def insertionSort(a,n,g):
  global count
  for i in range(g,n):
    v = a[i]
    j = i - g
    while j >= 0 and a[j] > v:
      a[j+g] = a[j]
      j = j - g
      count += 1
    a[j+g] = v

import sys
n = int(input())
a = list(map(int,sys.stdin))
count = 0
g = [88573,29524,9841,3280,1093,364,121,40,13,4,1]
g = [i for i in g if i <= n]
for i in range(len(g)):
  insertionSort(a,n,g[i])
print(len(g))
print(' '.join(map(str,g)))
print(count)
for i in range(n):
  print(a[i])


Measured memory_bytes: 45472
#include<stdio.h>

int base[3];

int main(){
  int sc,in,i,out;
  char ev[10];
  scanf("%d",&in);
  for(i=0,out=0,sc=0;i<in;){
    scanf("%s",ev);
    if(ev[0]=='O'){
      if(out==2){
	printf("%d\n",sc);
	sc=0;
	base[0]=base[1]=base[2]=0;
	i++;
      }
      out=(out+1)%3;
    }else if(ev[1]=='I'){
      sc+=base[2];
      base[2]=base[1];
      base[1]=base[0];
      base[0]=1;
    }else{
      sc+=base[0]+base[1]+base[2]+1;
      base[0]=base[1]=base[2]=0;
    }
  }
  return 0;
}

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

int main() {
    int p[3], j[2];
    cin >> p[0] >> p[1] >> p[2] >> j[0] >> j[1];
    sort(p, p+3);
    sort(j, j+2);
    cout << p[0] + j[0] - 50 << endl;
    return 0;
}

Measured memory_bytes: 0
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<math.h>
#include<bitset>
#include<random>
#include<set>
#include <cstdint>
#include<tuple>
using namespace std;
using ll = __int64_t;
using lll = __int128_t;
typedef pair<ll,ll> P;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
const ll longinf=1ll<<60;
const int inf=(1<<30)-1;
const ll mod=1e9+7;
vector<pair<ll,ll>> primeFactorDecomp(ll n){
      vector<pair<ll,ll>> ret;
      ll m=n;
      for(ll i=2;i*i<=m;i++){
            if(n%i!=0) continue;
            int cnt=0;
            while(n%i==0){
                  cnt++;
                  n/=i;
            }
            ret.push_back({i,cnt});
      }
      if(n>1){
            ret.push_back({n,1});
      }
      return ret;
}
int main(void){
  int n,m;
  cin>>n>>m;
  int a[m],b[m];
  int openby[m];
  vector<int> c[m];
  fill(openby,openby+m,0);
  rep0(i,m){
    cin>>a[i]>>b[i];
    rep0(j,b[i]){
      int d;
      cin>>d;
      --d;
      c[i].push_back(d);
    }
  }
  //rep0(i,m) cout<<openby[i]<<endl;
  int dp[m+1][(1<<n)];
  fill(dp[0],dp[m+1],inf);
  dp[0][0]=0;
  rep0(i,m){
    rep0(j,(1<<n)){
      int l=j;
      int d=c[i].size();
      dp[i+1][j]=min(dp[i][j],dp[i+1][j]);
      rep0(k,d){
      int h=(1<<c[i][k]);
      l|=h;
      dp[i+1][l]=min({dp[i][j]+a[i],dp[i+1][l],dp[i][l]});
      }
    }
  }
  int ans=dp[m][(1<<n)-1];
  /*rep0(i,m+1){
    rep0(j,(1<<n)){
      cout<<dp[i][j]<<" ";
    }
    cout<<endl;
  }*/
  if(ans!=inf) cout<<dp[m][(1<<n)-1]<<endl;
  else cout<<-1<<endl;
  return 0;
}


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

int main() {
  string n;
  cin >> n;
  
  int x = 0;
  for(int i = 0; i < n.size() ; i++) {
    if (n[i] == '1') {
      x++;
    }
  }
  
  cout << x << endl;
  
}

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

int main() {
  int K;
  cin >> K;
  if (K <= 9) {
    cout << K << endl;
  }
  else {
    queue<int64_t> q;
    for(int i = 1; i < 10; i++) {
      q.push(i);
    }
    K -= 9;
    while(1) {
      int64_t a = q.front();
      if (a % 10 != 0) {
        q.push(a * 10 + a % 10 - 1);
        K--;
        if (K == 0) {
          cout << a * 10 + a % 10 - 1 << endl;
          break;
        }
      }
      q.push(a * 10 + a % 10);
      K--;
      if (K == 0) {
        cout << a * 10 + a % 10 << endl;
        break;
      }
      if (a % 10 != 9) {
        q.push(a * 10 + a % 10 + 1);
        K--;
        if (K == 0) {
          cout << a * 10 + a % 10 + 1 << endl;
          break;
        }
      }
      q.pop();
    }
  }
}

Measured memory_bytes: 4100
<?php
  list($n,$k) = explode(" ", trim(fgets(STDIN)));

  $a = explode(" ", trim(fgets(STDIN)));

  $minus=[];
  $plus=[];
  $zero=false;
  for($i=0;$i<$n;$i++){
    if($a[$i] == 0){
      $k--;
      unset($a[$i]);
    }
  }

  sort($a);

  $dist=0;
  for($i=1;$i<$k;$i++){
    $dist+=abs($a[$i]-$a[$i-1]);
  }
//  echo $dist.PHP_EOL;
  if($a[$k-1] < 0){
    $min=$dist+abs($a[$k-1]);
  }else{
    if($a[0] < 0){
      $min=$dist+min(abs($a[$k-1]), abs($a[0]));
    }else{
      $min=$dist+abs($a[0]);
    }
  }
//  echo $min.PHP_EOL;


  for($i=$k;$i<$n;$i++){
    $dist-=abs($a[$i-$k+1]-$a[$i-$k]);
    $dist+=abs($a[$i]-$a[$i-1]);

    if($a[$i] < 0){
      $x=$dist+abs($a[$i]);
    }else{
      if($a[$i-$k+1] < 0){
        $x=$dist+min(abs($a[$i]), abs($a[$i-$k+1]));
      }else{
        $x=$dist+abs($a[$i-$k+1]);
      }
    }
//    echo $min." ".$x.PHP_EOL;
    $min = min($min,$x);
  }
  echo $min;

Measured memory_bytes: 23884
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a : A) cin >> a;} 


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

int N; cin >> N;
VI X(N+1);
rep(i, 1, N+1){
    int p; cin >> p;
    X[p] = i;
}
int mlen = 0;
int len = 1;
rep(i, 1, N){
    if (X[i] < X[i+1]) ++len;
    else {
        mlen = max(mlen, len);
        len = 1;
    }
}

cout << N - max(mlen, len) << "\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
	int a, b, c, i, copy;
	
	scanf("%d %d %d", &a, &b, &c);
	
	if (b > c){
		copy = b;
		b = c;
		c = copy;
	}
	
	if (a > b){
		copy = a;
		a = b;
		b = copy;
	}
	
	if (b > c){
		copy = b;
		b = c;
		c = copy;	
	}
	printf("%d %d %d\n", a, b ,c);
	
	return(0);
}

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

   typedef long long ll;
   typedef pair<ll, ll> Pii;

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair

   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
   template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

   ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
   ll pow(ll a, ll b){if (b == 0) return 1; else if (b % 2 == 0) return pow(a * a, b / 2); else return pow(a * a, b / 2) * a;}


   ll dx[4]={1,0,-1,0};
   ll dy[4]={0,1,0,-1};
const ll MAX_K = 1e5, MAX_N = 100;
ll N, K;
ll a[MAX_N] = {};
ll dp[MAX_K + 1] = {};
int main(){
  cin >> N >> K;
  REP(i, N){
    cin >> a[i];
  }
  REP(n, K + 1){
    ll i = 0;
    while(a[i] <= n && i < N){
      if (dp[n - a[i]] == 0){
        dp[n] = 1;
        break;
      }
      i++;
    }
  }
  /*
  REP(n, K + 1){
    printf("dp[%lld] = %lld\n", n, dp[n]);
  }
  */
  (dp[K] == 1) ?( cout << "First\n")  : (cout << "Second\n") ;
}


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

int main() {
  int N;
  cin >> N;
  
  vector<int> d(N);
  for(int i = 0; i < N; i++) {
    cin >> d.at(i);
  }
  
  vector<int> flag(101); // dは100まで
  for (int i = 0; i < N; i++) {
    flag.at(d.at(i)) = 1;
  }
  
  int ans = 0;
  for (int i = 0; i < 101; i++) {
    ans += flag.at(i);
  }
  
  cout << ans << endl;
}

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

int main() {
  int h,n;
  cin >> h >> n;
  vector<int> a(n);
  int sum = 0;
  for(int i = 0;i<n;i++) {
    cin >>a[i];
    sum +=a[i];
  }
  if(sum>=h) {
    cout << "Yes" <<endl;
  }
  else {
    cout << "No" <<endl;
  }
}

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

int n;

struct node
{
	int id, pid, k, d;
	int* cid;
	string type;
}N[100005];

void GetDepth(node& GN)
{
	GN.d = 0;
	node temp = GN;

	while (temp.pid != -1)
	{
		GN.d++;
		temp = N[temp.pid];
	}
}

void GetType(node& GN)
{
	if (GN.pid == -1)
		GN.type = "root";
	else if (GN.k == 0)
		GN.type = "leaf";
	else
		GN.type = "internal node";
}

void print()
{
	for (int i = 0; i < n; i++)
	{
		cout << "node " << N[i].id << ": " << "parent = " << N[i].pid << ", " << "depth = " << N[i].d << ", " << N[i].type << ", " << "[";

		if (N[i].k != 0)
		{
			for (int j = 0; j < N[i].k - 1; j++)
				cout << N[i].cid[j] << ", ";
			cout << N[i].cid[N[i].k - 1];
		}

		cout << "]" << endl;
	}	
}

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

	int place;
	cin >> n;
	
	for (int i = 0; i < n; i++)
		N[i].pid = -1;
	
	for (int i = 0; i < n; i++)
	{
		cin >> place;
		N[place].id = place;
		cin >> N[place].k;

		if (N[place].k > 0)
			N[place].cid = new int[N[place].k];

		for (int j = 0; j < N[place].k; j++)
		{
			cin >> N[place].cid[j];
			N[N[place].cid[j]].pid = N[place].id;
		}			
	}

	for (int i = 0; i < n; i++)
	{
		GetDepth(N[i]);
		GetType(N[i]);
	}

	print();

	return 0;
}



Measured memory_bytes: 11464
#include <iostream>
#include <string>
#include <cstdint>
#include <cmath>
#include <vector>
#include <map>
#include <climits>
#include <numeric>
#include <algorithm>

using namespace std;

struct Cerulean {
    int64_t pos = 0;
    int64_t hp = 0;
    int64_t damage = 0;
};

constexpr int64_t attack_count(int64_t hp, int64_t atk)
{
    return hp < 0 ? 0 : (hp / atk + (hp % atk ? 1 : 0));
}

constexpr int64_t enough_damage(int64_t hp, int64_t atk)
{
    return hp < 0 ? 0 : (hp + (hp % atk == 0 ? 0 : atk - hp % atk));
}

int main()
{
    int64_t N,D,A;
    cin >> N >> D >> A;
    vector<Cerulean> ceruleans(N);
    for(auto& c : ceruleans) cin >> c.pos >> c.hp;
    sort(begin(ceruleans), end(ceruleans), [](const auto& x, const auto& y){ return x.pos < y.pos; });
    if(D > 0){
        size_t i = 0;
        size_t j = 1;
        int64_t damage = enough_damage(ceruleans[0].hp, A);
        for(; j < ceruleans.size(); ){
            while(ceruleans[j].pos - ceruleans[i].pos > 2 * D){
                damage -= enough_damage(ceruleans[i].hp - ceruleans[i].damage, A);
                ++i;
            }
            ceruleans[j].damage = damage;
            damage += enough_damage(ceruleans[j].hp - ceruleans[j].damage, A);

            ++j;
        }
    }
    
    int64_t count = 0;
    for(size_t i = 0; i < ceruleans.size(); ++i){
        count += attack_count(ceruleans[i].hp - ceruleans[i].damage, A);
    }
    cout << count << '\n';
    
    //for(auto& c : ceruleans) cout << c.pos << ' ' << c.hp << '\n';
}
/*
2 * * * 4       2
----------------------
1 2 3 4 5 6 7 8 9 10
*/


Measured memory_bytes: 4992
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();

        int left = a + b;
        int right = c + d;

        if (left < right) {
            System.out.println("Right");
        } else if (left == right) {
            System.out.println("Balanced");
        } else {
            System.out.println("Left");
        }
    }
}


Measured memory_bytes: 22996
int main(int argc, const char * argv[]) {
    long int m;
    long int n;
    long int k;
    scanf("%ld%ld%ld", &m, &n, &k);
    if (k > m) {
        k = k - m;
        m = 0;
    }
    else {
        m = m - k;
        k = 0;
    }
    n = ((n - k) > 0) ? (n - k) : 0;
    printf("%ld %ld", m, n);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  int N;
  int Alice = 0, Bob = 0;
  cin >> N;
  vector<int> a(N);
  for(int i = 0; i < N; i++){
    cin >> a[i];
  }
  
  sort(a.rbegin(),a.rend());

  /*for(int i = 0; i < N; i++){
    cout << a[i] << " ";
  }
  cout << endl;*/

  for(int i = 0; i < N; i++){
    if(i % 2 == 0){
      Alice = Alice + a[i]; 
      //cout << i << " " << Alice << endl;
    } else {
      Bob = Bob + a[i];
      //cout << i << " " << Bob << endl;
    }
  }
  int ans = 0;
  ans = Alice - Bob;
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

const int DAYS[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

struct Date {
	int y;
	int m;
	int d;
	Date() {}
	Date(int y, int m, int d) : y(y), m(m), d(d) {}
};

bool isLeap(int y)
{
	if (y % 400 == 0) return true;
	else if (y % 100 == 0) return false;
	else if (y % 4 == 0) return true;
	else return false;
}

int countRestDays(int y, int m, int d)
{
	int res = DAYS[m-1] - d + 1;
	for (int i=m; i<12; i++) {
		res += DAYS[i];
	}
	if (isLeap(y) && m <= 2) res++;
	return res;
}

int main()
{
	int y1, m1, d1, y2, m2, d2;
	while (std::cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2) {
		if (y1==-1) break;
		int res = countRestDays(y1, m1, d1);
		for (int y=y1+1; y<=y2; y++) {
			res += isLeap(y) ? 366 : 365;
		}
		res -= countRestDays(y2, m2, d2);
		std::cout << res << std::endl;
	}
	return 0;
}




Measured memory_bytes: 2992
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner stdIn = new Scanner(System.in);
		String S = stdIn.nextLine();
		String T = stdIn.nextLine();
		
		char[] s = S.toCharArray();
		char[] t = T.toCharArray();
		
		int minCount = 1000;
		
		for(int i = 0; i < s.length - t.length + 1; i ++) {
			int counter = 0;
			for(int j = 0; j < t.length; j ++) {
				if(s[i + j] != t[j]) {
					counter ++;
				}
				if(minCount <= counter) {
					break;
				}
			}
			minCount = Math.min(minCount, counter);
		}
		
		System.out.println(minCount);
	}
}


Measured memory_bytes: 35956
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  string s;
  cin >> s;
  int mm = stoi(s.substr(5,2));
    if(mm<=4){
      cout << "Heisei" << endl;
    }else{
      cout << "TBD" << endl;
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  //input
  int N,x,y; cin>>N;
  x=(N/100%10)*100+(N/100%10)*10+(N/100%10);
  y=(N/100%10)*100+(N/100%10)*10+(N/100%10)+111;
  if(N<=x){
    cout<<x<<endl;
  }else{
    cout<<y<<endl;
  }
}
  



Measured memory_bytes: 256
#include<stdio.h>
int main()
{

    int n,x=0,max;
    while(scanf("%d",&n)!=EOF){
            max=0;
    char s[n];
    scanf("%*[\n]%[^\n]",s);
    for(int i=0;i<n;i++){
            if(s[i]=='I')
            x++;
        else if(s[i]=='D')
            x--;
        if (max < x) max = x;
    }
    printf("%d\n",max);
    }
    return 0;
}


/*
*/


Measured memory_bytes: 1732
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;
typedef pair <int, int> P;

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

    int n, k;
    cin >> n >> k;

    if (k > (n - 1) * (n - 2) / 2) {
        cout << -1 << '\n';
        return 0;
    }

    int diff = (n - 1) * (n - 2) / 2 - k;

    cout << n - 1 + diff << '\n';

    for (int i = 2; i <= n; i++) {
        cout << 1 << " " << i << '\n';
    }

    vector <P> vec;
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j < i; j++) {
            vec.push_back(P(i, j));
        }
    }

    int idx = 0;
    while (diff) {
        cout << vec[idx].first << " " << vec[idx].second << "\n";
        idx++;
        diff--;
    }

    return 0;
}

Measured memory_bytes: 384
x1, y1, x2, y2 = map(int,input().split())
x = x1 - x2
y = y1 - y2
x3, y3 = x2 + y, y2 - x
x4, y4 = x1 + y, y1 - x
print(x3, y3, x4, y4)


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#include <cassert>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define Cout(x) cout << x << endl;
#define check(v) rep(i,v.size()) cout << v[i] << endl;
#define vint(x) vector<int> x
#define vll(x) vector<long long> x
#define vstr(x) vector<string> x
const long long LLINF = 1LL<<60;
const int INF = 1e9;
const long long MOD = 1000000007;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
#define pint pair<int,int>
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int n, k;
ll ans;
vector<int> tree[100005];
ll fact(int num, int time) {
    ll ret = 1;
    for (int i = num; i > num-time; i--) {
        ret *= i;
        ret %= MOD;
    }
    return ret;
}
void dfs(int now, int par) {
    int chl = tree[now].size();
    if(chl>=k) ans = 0;
    ans *= fact(k-2,chl-1);
    ans %= MOD;
    rep(i,tree[now].size()) {
        if(tree[now][i] == par) continue;
        dfs(tree[now][i], now);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    rep(i,n-1) {
        int a, b; cin >> a >> b;
        a--; b--;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    ans = fact(k,(int)tree[0].size()+1);

    rep(i,tree[0].size()) {
        dfs(tree[0][i],0);
    }
    cout << ans << endl;

    return 0;
}

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

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

    int h, w;
    cin >> h >> w;
    
    vector<int> cnt(26, 0);
    for(int i = 0; i < h; ++i){
        string s;
        cin >> s;
        for(int j = 0; j < s.size(); ++j) ++cnt[s[j] - 'a'];
    }

    sort(cnt.begin(), cnt.end(), greater<int>());

    if(h*w < 4){
        if(h*w == 1) cout << "Yes" << endl;
        else{
            if(cnt[0] == 2) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        return 0;
    }

    if(h%2==0 && w%2==0){
        for(int i = 0; i < 26; ++i){
            if(cnt[i] > 0 && cnt[i]%4 != 0){
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;

        return 0;
    }

    else{
        int need4, need2, any;
        if(h%2==1 && w%2==1){
            need4 = (h/2*2) * (w/2*2) / 4;
            need2 = h/2 + w/2;
            any = 1;
        }
        else{
            need4 = (h/2*2) * (w/2*2) / 4;
            if(h%2 == 1) need2 = w/2;
            else need2 = h/2;
            any = 0;
        }
        
        int cnt4 = 0;
        int cnt2 = 0;
        int cnta = 0;
        for(int i = 0; i < 26; ++i){
            int tmp = cnt[i];
            if(tmp % 4 == 0) cnt4 += tmp/4;
            else if(tmp % 2 == 0){
                ++cnt2;
                cnt4 += (tmp-2) / 4;
            }
            else{
                ++cnta;
                --tmp;
                cnt4 += tmp/4;
                cnt2 += tmp%4;
            }
        }


        if(cnta != any){
            cout << "No" << endl;
            return 0;
        }
        if(need4 == cnt4){
            if(need2 == cnt2) cout << "Yes" << endl;
            else cout << "No" << endl;
            return 0;
        }
        else{
            if(need4 > cnt4) cout << "No" << endl;
            else if(cnt2 + (cnt4-need4)*2 == need2) cout << "Yes" << endl;
            return 0;
        }

    }
    
    return 0;

}

Measured memory_bytes: 3652
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>

using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7; 
const int MINF = -1050000000;


int main() {
	
	int n;
	cin >> n;
	vector<ll> a(n);
	vector<ll> s(n + 1, 0);

	rep(i, n) {
		cin >> a[i];
		s[i + 1] = s[i] + a[i];
	}

	ll dif = s[n];
	for(int i = 0; i < n; i++) {
		dif = min(abs(s[i] - (s[n] - s[i])), dif);
	}

	cout << dif << endl;
	return 0;
}


Measured memory_bytes: 3328
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] S = sc.next().toCharArray();
        int len = S.length;
        long ans = 0;
        long bCnt = 0;
        for(int i = 0; i < len; i++){
            if(S[i] == 'B'){
                ans += len -1 -i;
                bCnt++;
            }
        }
        bCnt--;
        ans -= (1+bCnt)*bCnt/2;
        System.out.println(ans);

        sc.close();
    }

}


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

#define int long long

signed main() {
    string s, t;
    cin >> s >> t;
    if(s.size() < t.size()) {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    vector<string> ans;
    bool f1 = false;
    for(int i=0; i<s.size(); ++i) {
        bool f = true;
        for(int j=0; j<t.size(); ++j) {
            if(s[i+j]!='?'&&s[i+j]!=t[j]) {
                f = false;
                break;
            }
        }
        if(f) {
            f1 = true;
            string s2 = s;
            for(int j=0; j<t.size(); ++j) {
                s2[i+j] = t[j];
            }
            ans.push_back(s2);
        }
    }
    if(!f1) {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    sort(ans.begin(), ans.end());
    string u = ans[0];
    for(int i=0; i<u.size(); ++i) {
        if(u[i]=='?') u[i] = 'a';
    }
    cout << u << endl;
    return 0;
}



Measured memory_bytes: 256
// https://atcoder.jp/contests/dp/tasks/dp_g
#include <iostream>
#include <map>
#include <vector>
#include <stack>
using namespace std;

int N, M;
map<int, vector<int>> adjlist;
map<int, int> memo;

int depth(int start) {
    if (memo.find(start) != memo.end())
        return memo[start];

    int res = 0;
    for (auto& next: adjlist[start]) {
        res = max(res, 1 + depth(next));
    }
    return memo[start] = res;

}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int tmpx, tmpy;
        cin >> tmpx >> tmpy;
        adjlist[tmpx].push_back(tmpy);
        }

    // for(int i = 1; i <= N; ++i) {
    //     cerr << "adjlist[" << i << "] = ";
    //     for(auto& x: adjlist[i])
    //         cerr << x << " ";
    //     cerr << endl;
    // }

    int res = 0;
    for (int i = 1; i <= N; ++i)
        res = max(res, depth(i));

    // for(int i = 1; i <= N; ++i) {
    //     cerr << "memo[" << i << "] = " << memo[i] << endl;
    // }
    cout << res << endl;


    return 0;
}

Measured memory_bytes: 19328
N = int(input())
# スペース区切りの整数をリストに入力

sdic = {}

nMax = 1

for i in range(N):
    s = str(input())
    if s in sdic:
        sdic[s] += 1
        nMax = max(nMax,sdic[s])
    else:
        sdic[s] = 1

slist = []
for k in sdic:
    if sdic[k] == nMax:
        slist.append(k)

for s in sorted(slist):
    print(s)


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    i64 N; cin >> N;
    if (N == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<i64> nbin;
    while (N != 0) {
        i64 rem = abs(N % 2);
        nbin.pb(abs(rem));
        N -= rem;
        N /= -2;
    }

    for (auto it = nbin.rbegin(); it != nbin.rend(); it++) {
        cout << *it;
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;

typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

long long int DP[2100][2100] = {};
long long int DPs[2100][2100] = {};

int main(){
    int N, M;
    cin >> N >> M;
    int S[2100], T[2100];
    for(int i = 1; i <= N; i++){
        cin >> S[i];
    }
    for(int i = 1; i <= M; i++){
        cin >> T[i];
    }
    for(int i = 1; i <= N; i++){
        long long int SS = 0;
        for(int j = 1; j <= M; j++){
            if(S[i] == T[j]){
                DP[i][j] = DPs[i - 1][j - 1] + 1;
                DP[i][j] %= MOD;
                SS += DP[i][j];
                SS %= MOD;
            }
            DPs[i][j] = DPs[i - 1][j] + SS;
            DPs[i][j] %= MOD;
        }
    }

    long long int ans = 0;
    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= M; j++){
            ans += DP[i][j];
            ans %= MOD;
        }
    }
    cout << (ans + 1) % MOD << endl;
    return 0;
}

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

struct card {
    string s;
    bool operator<(const card& rhs) {
        return s[1] < rhs.s[1];
    }
};

using vc = vector<card>;

int bubbleSort(vc& a) {
    bool change = 1;
    int cnt = 0;
    while (change) {
        change = 0;
        for (int j = a.size() - 1; j >= 1; j--) {
            if (a[j] < a[j - 1]) {
                swap(a[j], a[j - 1]);
                cnt++;
                change = 1;
            }
        }
    }
    return cnt;
}

int selectionSort(vc& a) {
    int cnt = 0;
    for (int i = 0; i < a.size(); i++) {
        int minj = i;
        for (int j = i; j < a.size(); j++) {
            if (a[j] < a[minj]) {
                minj = j;
            }
        }
        if (i != minj) {
            swap(a[i], a[minj]);
            cnt++;
        }
    }
    return cnt;
}

void printvec(vc& x, int size = 0) {
    cout << x.front().s;
    for (int i = 1; i < (size == 0 ? x.size() : size); i++) {
        cout << " " << x[i].s;
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    vc as;
    string order[10];
    for (int i = 0; i < 9; i++) {
        order[i] = "";
    }
    for (int i = 0; i < n; i++) {
        string a;
        cin >> a;
        as.push_back({a});
        order[a[1] - '0'] += a[0];
    }
    vc bs(as), cs(as);
    bubbleSort(bs);
    string orderb[10];
    for (int i = 0; i < 10; i++) {
        orderb[i] = "";
    }
    for (int i = 0; i < bs.size(); i++) {
        orderb[bs[i].s[1] - '0'] += bs[i].s[0];
    }
    int ok = true;
    for (int i = 0; i < 10; i++) {
        if (order[i] != orderb[i]) ok = false;
    }
    printvec(bs);
    cout << (ok ? "Stable" : "Not stable") << endl;

    selectionSort(cs);
    string orderc[10];
    for (int i = 0; i < 10; i++) {
        orderc[i] = "";
    }
    for (int i = 0; i < cs.size(); i++) {
        orderc[cs[i].s[1] - '0'] += cs[i].s[0];
    }
    ok = true;
    for (int i = 0; i < 10; i++) {
        if (order[i] != orderc[i]) ok = false;
    }
    printvec(cs);
    cout << (ok ? "Stable" : "Not stable") << endl;
}


Measured memory_bytes: 3216
#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
     
    int main() {
    	int h;
    	cin >> h;
    	int w;
    	cin >> w;
    	vector<string> a(h);
    	for (int i = 0; i < h; i++) {
    		cin >> a[i];
    	}
     
    	vector<bool> row(h, false);
    	vector<bool> col(w, false);
    	for (int i = 0; i < h; i++) {
    		for (int j = 0; j < w; j++) {
    			if (a[i][j] == '#') {
    				row[i] = true;
    				col[j] = true;
    			}
    		}
    	}
     
    	for (int i = 0; i < h; i++) {
    		if (row[i]) {
    			for (int j = 0; j < w; j++) {
    				if (col[j]) {
    					cout << a[i][j];
    				}
    			}
    			cout << endl;
    		}
    	}
    }

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>

using namespace std;

#define rep(i,a,n) for(int (i)=a;(i)<(int)(n);(i)++)
#define rrep(i,a,n) for(int (i)=(n)-1;(i)>=a;(i)--)
#define all(x) (x).begin(),(x).end()

typedef long long ll;

int main() {
	int a,b;
	int d,r;
	double f;

	cin >> a >> b;

	d = a / b;
	r = a % b;
	f = (double) a / b;

	printf("%d %d %0.6f\n", d, r, f);
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    int n;cin>>n;
    vi a(n);
    map<int,int>b;
    rep(i,n){
        cin>>a[i];
        if(i%2==1)b[a[i]]=1;
        else b[a[i]]=0;
    }
    sort(all(a));
    int cnt=0;
    rep(i,n){
        if(i%2!=b[a[i]])cnt++;
    }
    cout<<cnt/2<<endl;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define pb(x) push_back(x)
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pcc pair<char, char>
#define pdd pair<double, double>
#define mll map<long long, long long>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define flsh fflush(stdout)
#define gcd __gcd
#define clr(x) memset(x, 0, sizeof(x))
#define mod 1000000007LL
#define mod2 998244353LL
#define INF 1000000000007
 

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> o_tree;


void solve()
{
    ll a;
    cin>>a;
    cout<<(a+a*a+a*a*a)<<"\n";
}


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


if (fopen("input.txt","r" ))
  {
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
  }
cout<<setprecision(20);


ll t=1;


// cin>>t;


while(t--)
{
solve();
} 


return 0;
}

Measured memory_bytes: 3656
l = str(input())
cnt = 1
month=""
day=""
for i in l:
    if 6<=cnt and cnt<=7:
        month += str(i)
    elif 9<=cnt and cnt<=10:
        day += str(i)
    cnt += 1

month_int = int(month)
day_int = int(day)

if month_int <=4:
    print("Heisei")
else:
    print("TBD")


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long int
map<int,int> mp;
int mod=1e11;
int32_t main()
{
    int h;
    cin>>h;
    int n;
    cin>>n;
    vector<int> vec,val;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        vec.push_back(x);
        val.push_back(y);
    }
    vector<vector<int> > dp(h+1,vector<int> (n+1,mod));
    for(int i=0;i<n;i++)
    dp[0][i]=0;
    for(int i=1;i<=h;i++)
    {
        if(i<=vec[0])
        dp[i][0]=val[0];
        else dp[i][0]=val[0]+dp[i-vec[0]][0];
        //cout<<dp[i][0]<<endl;
    }
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<n;j++)
        {
            int mini=mod;
            if(i-vec[j]>=0)
            {
                mini=min(mini,dp[i-vec[j]][j]+val[j]);
            }
            else
            mini=min(mini,val[j]);
            mini=min(mini,dp[i][j-1]);
            dp[i][j]=mini;
        }
    }
    cout<<dp[h][n-1]<<endl;
}

Measured memory_bytes: 78848
#include<cstdio>
#include<iostream>
using namespace std;
int d[11][11],n,m,tot,now,sum;
int pa[110],pb[110];
bool vis[11][11];
struct edg{
    int a,b,c;
}ans[310];
void print()
{
    int numn=0,numm=0;
    for (int i=1;i<=sum;i++)
    {
        numm+=ans[i].a+ans[i].b+1;
        numn+=ans[i].a+ans[i].b;
    }
    numn+=2;
    if (numn>300) {while(1);printf("Impossible\n");return;}
    printf("Possible\n");
    printf("%d %d\n",numn,numm);
    int t=1,pre=1;
    for (int i=1;i<=sum;i++)
    {
        pre=1;
        printf("%d %d %d\n",pre,++t,ans[i].c),pre=t;
        for (int j=1;j<=ans[i].a;j++)
        {
            printf("%d %d %c\n",pre,(j==ans[i].a&&ans[i].b==0)?numn:++t,'X'),pre=t;
        }
        for (int j=1;j<=ans[i].b;j++)
            printf("%d %d %c\n",pre,(j==ans[i].b)?numn:++t,'Y'),pre=t;

    }
    printf("%d %d\n",1,numn);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&d[i][j]);
    for (int s=0;s<=300;s++)
        for (int a=0;a<=s&&a<=100;a++)
            for (int b=0;b<=s-a&&b<=100;b++)
                {
                    int c=s-a-b;
                    bool p=0,q=0;
                    int now=0;
                    for (int i=1;i<=n;i++)
                    {
                        for (int j=1;j<=m;j++)
                        {
                            if (a*i+b*j+c==d[i][j]&&!vis[i][j]) q=1,now++,pa[now]=i,pb[now]=j;
                            else if (a*i+b*j+c<d[i][j]) {p=1;break;}
                        }
                        if (p==1) break;
                    }
                    if ((!p)&&q) 
                    {
                        for (int i=1;i<=now;i++)
                            vis[pa[i]][pb[i]]=1;
                        tot+=now,ans[++sum].a=a,ans[sum].b=b,ans[sum].c=c;
                        if (tot==n*m){print();return 0;}
                    }
                }
    printf("Impossible\n");
}
/*--------------------- 
作者：Fizzmy 
来源：CSDN 
原文：https://blog.csdn.net/Charlie_jilei/article/details/79132120 
版权声明：本文为博主原创文章，转载请附上博文链接！*/

Measured memory_bytes: 256
def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        x, y = y, x % y
    return x

a,b,c = map(int,input().split())
if a == b:
    if c % a == 0:
        print('YES')
    else:
        print('NO')
else:
    if c % gcd(a, b) == 0:
        print('YES')
    else:
        print('NO')


Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int main() {
	int n; cin >> n;
	int a[100];
	rep(i, n) {
		cin >> a[i];
	}
	sort(a, a + n);
	cout << a[n - 1] - a[0] << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int comp(const void* a, const void* b)  
{ return *(int*)a > *(int*)b ; }  
  
// Function to count all possible triangles with arr[]  
// elements  
int findNumberOfTriangles(int arr[], int n)  
{  
    qsort(arr, n, sizeof( arr[0] ), comp);  
    int count = 0;  
    for (int i = 0; i < n - 2; ++i)  
    {  
        int k = i + 2;  
        for (int j = i + 1; j < n; ++j)  
        {  
            while (k < n && arr[i] + arr[j] > arr[k])  
            ++k;  
            if(k > j)  
            count += k - j - 1;  
        }  
    }  
  
    return count;  
}
int main(){
    int n,i;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<findNumberOfTriangles(a,n);
    return 0;
}

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

int main()
{
    int n, a[100];
    while(cin >> n && n) {
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        int ret = 0;
        for(int i = 0; i < n - 1; i++) {
            for(int j = 0; j < n - 1 - i; j++) {
                if(a[j] > a[j + 1]) {
                    swap(a[j], a[j + 1]);
                    ret++;
                }
            }
        }
        cout << ret << endl;
    }
}

Measured memory_bytes: 0
import sys
input=sys.stdin.buffer.readline
import os
from math import*


w,h,x,y=map(int,input().split())
area=w*h
#ans1=min((w*y),(area-(w*y)))
#ans2=min((x*h),(area-(x*h)))
#if ans1==ans2:
#	print(ans1,1)
#else:
#	print(max(ans1,ans2),0)
print((area/2),1 if x==w/2 and y==h/2 else 0)



Measured memory_bytes: 62004
#include <iostream>
#include <string>

bool isEven(const std::string a, int pos) {
    for (int i = 0; i < pos; i++) {
        if (a[i] != a[i + pos]) return false;
    }
    return true;
}

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

    std::string s; std::cin >> s;
    int pos = (s.size() - 1) / 2;
    while (pos) {
        if (isEven(s, pos)) break;
        pos--;
    }
    std::cout << (pos * 2) << std::endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
        final int N = s.nextInt();
        final int K = s.nextInt();
        Set nSet = new HashSet();
        int[] kHoji;

        // 菓子の種類ループ
        for (int i = 0 ; i < K ; i++) {
            // 菓子の個数入力
            int kNum = s.nextInt();
            kHoji = new int[kNum];
            for (int j = 0 ; j < kHoji.length ; j++) {
                nSet.add(s.nextInt());
            }
            // System.out.println(i);
        }
        System.out.println(N - nSet.size());
  }
}

Measured memory_bytes: 37524
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <memory.h>
#include <math.h>

int gcd(int a, int b)
{
    int r;

    if (a < b) {return gcd(b, a);}

    if (b == 0) {return a;}

    do {
        r = a % b;
        a = b;
        b = r;
    } while(r);

    return a;
}

int main(int argc, char *argv[])
{
    int n;
    int a[100000];
    int l[100001];
    int r[100001];
    int val;
    int i;
    int ans;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    l[0] = 0;
    for (i = 1; i < n; i++) {
        l[i] = gcd(l[i - 1], a[i - 1]);
    }

    r[n - 1] = 0;
    for (i = n - 2; i >= 0; i--) {
        r[i] = gcd(r[i + 1], a[i + 1]);
    }

    ans = 0;
    for (i = 0; i < n; i++) {
        val = gcd(l[i], r[i]);
        if (val > ans) {ans = val;}
    }

    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 1280
import numpy as np


def main():
    N, K = [int(x) for x in input().split()]
    A = [float(x) for x in input().split()]
    F = [float(x) for x in input().split()]

    A = np.array(sorted(A))
    F = np.array(sorted(F, reverse=True))

    if K >= np.sum(A)*N:
        print(0)
        exit()

    min_time = 0
    max_time = A[-1] * F[0]

    while max_time != min_time:
        tgt_time = (min_time + max_time)//2
        ideal_a = np.floor(tgt_time*np.ones(N)/F)
        cost = A - ideal_a
        require_k = np.sum(cost[cost > 0])
        if require_k <= K:
            max_time = tgt_time
        else:
            min_time = tgt_time+1

    print(int(max_time))


if __name__ == "__main__":
    main()


Measured memory_bytes: 40404
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

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

#define MP make_pair
#define PB push_back

typedef pair<int, int> PII;

int main() {
	int m, n;
	bool flag;

	while (1) {
		vector<PII> seiza;
		set<PII> star;

		cin >> m;
		if (m == 0) break;
		REP(i, m) {
			int x, y;
			scanf("%d %d", &x, &y);
			seiza.PB(MP(x, y));
		}
		cin >> n;
		REP(i, n) {
			int x, y;
			scanf("%d %d", &x, &y);
			star.insert(MP(x, y));
		}


		for (set<PII>::iterator it = star.begin(); it != star.end(); it++) {
			PII target = *(it);
			int dx = target.first - seiza[0].first;
			int dy = target.second - seiza[0].second;

			flag = true;
			REP(j, m) {
				if (star.find(MP(seiza[j].first + dx, seiza[j].second + dy)) == star.end())
					flag = false;
			}
			if (flag) {
				printf("%d %d\n", dx, dy);
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1280
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define debug(v) cout << #v<< ": " << v <<endl;
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000000007;

int main(){
    string s; cin >> s;
    if(s == "RRR"){
        prtl(3);
    }else if(s == "SRR"||s == "RRS"){
        prtl(2);
    }else if(s == "SRS"|| s == "SSR"|| s == "RSS"|| s == "RSR"){
        prtl(1);
    }else{
        prtl(0);
    }
}


Measured memory_bytes: 3624
#include<stdio.h>
#include<string.h>
char srx[100001];
int main()
{
    gets(srx);
    int i,zjq=0;
    for(i=1;i<strlen(srx);i++)//注意从1开始，不然就会多一个
    if(srx[i]!=srx[i-1])
    zjq++;//判断成功就加1（还是C语言的char好用~，可以当数组用）
    printf("%d\n",zjq);//回车注意++
    return 0;
}

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

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

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

const double PI = acos(-1);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 300 + 47;
int dp[MAX][MAX][MAX];
string s;

void Max(int& key, int val)
{
	key = max(key, val);
}

int solve(int n, int cnt)
{
	FOR(i, 0, n)
	{
		dp[i][i][0] = 1;
	}

	FOR(len, 2, n + 1)
	{
		FOR(i, 0, n)
		{
			int j = i + len - 1;
			if (j >= n) break;
			FOR(k, 0, cnt + 1)
			{
				if (s[i] == s[j])
				{
					Max(dp[i][j][k], dp[i + 1][j - 1][k] + 2);
				}

				if (k) Max(dp[i][j][k], dp[i + 1][j - 1][k - 1] + 2);
				Max(dp[i][j][k], dp[i][j - 1][k]);
				Max(dp[i][j][k], dp[i + 1][j][k]);
			}
		}
	}

//	FOR(i, 0, n)
//	{
//		FOR(j, i, n)
//		{
//			FOR(k, 0, cnt + 1)
//			{
//				cout << i << " " << j << " " << k << ": " << dp[i][j][k] << endl;
//			}
//		}
//	}
	int ans = 0;
	FOR(k, 0, cnt + 1) Max(ans, dp[0][n - 1][k]);
	return ans;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0);
	int k, n;
	cin >> s >> k;
	n = SZ(s);
	int ans = solve(n, k);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 141312
#include <bits/stdc++.h>
using namespace std;
#define boost ios::sync_with_stdio(false);cin.tie(nullptr)
#define int long long
#define pi pair<int,int>
#define ff first
#define ss second
#include "string"

int lis(vector<int>&a){
	vector<int>dp;
	for(int &i:a){
		int tt = upper_bound(dp.begin(),dp.end(),i) - dp.begin();
		if(tt == dp.size())
			dp.push_back(i);
		else
			dp[tt] = i;
	}
	return dp.size();
}

int32_t main(){
	boost;
	int n;
	cin >> n;
	vector<int>a(n);
	for(int &i:a)
		cin>>i;
	reverse(a.begin(),a.end());
	int ans = lis(a);
	cout<<ans<<endl;
}



Measured memory_bytes: 4976