akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cmath>
using namespace std;
int a[100000],arr[100000],n;
int topdown(int x);
int main()
{
  int ans;
  cin>>n;
  for(int i=0;i<n;i++)
  {
   cin>>arr[i];
  }
  for(int i=0;i<n;i++)
  {
   a[i]=-1;
  }
  ans=topdown(0);
  cout<<ans;
  return 0;
  
}  
int topdown(int x)
{
 if(a[x]!=-1){return a[x];}
 if(x==n-3||x==n-2){a[x]=abs(arr[n-1]-arr[x]);return a[x];}
 int q;
 q=min(topdown(x+1)+abs(arr[x+1]-arr[x]),topdown(x+2)+abs(arr[x+2]-arr[x]));
 a[x]=q;
 return q;
}  
 

Measured memory_bytes: 2560
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
bool dp[101][101];
int main()
{
	ll x,y;
	cin>>x>>y;
	//実験コード
	// fill(dp[0],dp[101],false);
	// for(int i=2;i<101;i++)
	// {
	// 	for(int j=0;j<=i;j++)
	// 	{
	// 		//(i-j,j)のケースを調べる
	// 		if(i-j==1 && j==1)
	// 			continue;
	// 		bool f=false;
	// 		for(int k=1;k*2<=i-j;k++)
	// 			f|=!(dp[i-j-k*2][j+k]);
	// 		for(int k=1;k*2<=j;k++)
	// 			f|=!(dp[i-j+k][j-k*2]);
	// 		dp[i-j][j]=f;
	// 	}
	// }
	// for(int i=0;i<101;i++)
	// {
	// 	for(int j=0;j<101-i;j++)
	// 	{
	// 		// if(dp[i][j])
	// 		// 	cerr<<"A";
	// 		// else
	// 		// 	cerr<<"B";
	// 		if(!dp[i][j])
	// 		{
	// 			cerr<<i<<" "<<j<<endl;
	// 			//break;
	// 		}
	// 	}
	// 	//cerr<<endl;
	// }
	if(max(x,y)-min(x,y)<2)
		cout<<"Brown"<<endl;
	else
		cout<<"Alice"<<endl;
	return 0;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    for i in range(n):
        a = aa.pop(i)
        for j in range(i - 1, -1, -1):
            if aa[j] <= a:
                aa.insert(j + 1, a)
                break
        else:
            aa = [a] + aa
        print(*aa)

main()



Measured memory_bytes: 5988
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int nb;
    cin >> nb;
    vector<int> tab(nb);
    for(int i = 0; i < nb; i++)
        cin >> tab[i];
    int tot = 0;
    for(int i = 0; i < nb; i++){
        if(tab[i] == i+1){
            int tempo = tab[i];
            tab[i] = tab[i+1];
            tab[i+1] = tempo;
            tot++;
        }
    }
    cout << tot << endl;
}


Measured memory_bytes: 640
#include <stdio.h>          // printf(), scanf()

int
main(int argc, char **argv)
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		int x;
		scanf("%d", &x);

		printf("Case %d:\n", i);
		for (int j = 0; j < 10; ++j)
		{
			x = x * x;
			x = (x / 100) % 10000;
			printf("%d\n", x);
		}
	}

	return 0;
}

Measured memory_bytes: 1760
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define all(v) v.begin(), v.end()
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    vector<vector<int>> A(3,vector<int>(3));
    rep(i,3) {
        rep(j,3) {
            cin>>A.at(i).at(j);
        }
    }
    int N; cin>>N;
    vector<vector<bool>> C(3,vector<bool>(3,false));
    rep(i,N) {
        int n;
        cin>>n;
        rep(i,3) {
            rep(j,3) {
                if(A.at(i).at(j)==n) {
                    C.at(i).at(j)=true;
                }
            }
        }
    }
    bool ok=false;
    rep(i,3) {
        rep(j,3) {
            if(C.at(0).at(0)==true&&C.at(0).at(1)==true&&C.at(0).at(2)==true) ok=true;
            else if(C.at(1).at(0)==true&&C.at(1).at(1)==true&&C.at(1).at(2)==true) ok=true;
            else if(C.at(2).at(0)==true&&C.at(2).at(1)==true&&C.at(2).at(2)==true) ok=true;
            else if(C.at(0).at(0)==true&&C.at(1).at(1)==true&&C.at(2).at(2)==true) ok=true;
            else if(C.at(2).at(0)==true&&C.at(1).at(1)==true&&C.at(0).at(2)==true) ok=true;
            else if(C.at(0).at(0)==true&&C.at(1).at(0)==true&&C.at(2).at(0)==true) ok=true;
            else if(C.at(0).at(1)==true&&C.at(1).at(1)==true&&C.at(2).at(1)==true) ok=true;
            else if(C.at(0).at(2)==true&&C.at(1).at(2)==true&&C.at(2).at(2)==true) ok=true;
        }
    }
    if(ok) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 768
#include<iostream>
#include<map>
#include<set>
#include<cstdio>
#include<vector>
using namespace std;

map<string,bool> M;
map<string,bool>::iterator Mp;
vector<int> color;
string S;
bool cb[8];
int ans;

void Check(string S)
{
  string C=S;
  for(int i=0;i<4;i++){
    for(int i=0;i<4;i++){
      for(int i=0;i<4;i++){
	swap(C[0],C[1]);swap(C[1],C[5]);swap(C[5],C[4]);
	swap(C[3],C[2]);swap(C[2],C[6]);swap(C[6],C[7]);
	if(M[C])return;
      }
      swap(C[0],C[3]);swap(C[3],C[7]);swap(C[7],C[4]);
      swap(C[1],C[2]);swap(C[2],C[6]);swap(C[6],C[5]);
      if(M[C])return;
    }
    swap(C[0],C[1]);swap(C[1],C[2]);swap(C[2],C[3]);
    swap(C[4],C[5]);swap(C[5],C[6]);swap(C[6],C[7]);
    if(M[C])return;
  }
  M[C]=true;
  ans++;
}

void make(int i)
{
  S+=(color[i]+'0');
  if(S.length()==8){
    Check(S);
  }
  else {
    for(int i=0;i<8;i++){
      if(cb[i])continue;
      cb[i]=true;
      make(i);
      cb[i]=false;
    }
  }
  S.erase(S.begin()+S.length()-1);
}

int main()
{
  string s[8];
  while(cin>>s[0]){
    for(int i=0;i<7;i++)cin>>s[i+1];
    int a=1;
    map<string,int> m;
    color.clear();
    M.clear();
    m.clear();
    for(int i=0;i<8;i++){
      if(m[s[i]]==0){
	color.push_back(a);
	m[s[i]]=a;
	a++;
      }
      else color.push_back(m[s[i]]);
    }
    ans=0;
    for(int i=0;i<8;i++){
      S="";
      cb[i]=true;
      make(i);
      cb[i]=false;
    }
    cout<<ans<<endl;
  }
  return 0;
}

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

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

    int n, a, b;
    cin >> n >> a >> b;

    if (abs(a - b) % 2) cout << "Borys" << '\n';
    else cout << "Alice" << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define loop(i,a,b) for(i=a;i<b;i++)
#define rloop(i,a,b) for(i=a;i>=b;i--)
#define vi vector<int>
#define vs vector<string>
const int inf=1e9+1;
const ll INF=1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846

int main(){
	int n,i,j,temp;
	cin>>n;
	vi a(n);
	loop(i,0,n){
		cin>>a[i];
	}
	i=-1;
	int x=a[n-1];
	loop(j,0,n-1){
		if(a[j]<=x){
			i++;
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}
	}
	temp=a[i+1];
	a[i+1]=a[n-1];
	a[n-1]=temp;
	loop(j,0,n){
		if(j==i+1){
			cout<<"["<<a[j]<<"] ";
		}else if(j!=n-1){
			cout<<a[j]<<" ";
		}else{
			cout<<a[j]<<endl;
		}
	}
}

Measured memory_bytes: 3104
N, M = map(int, input().split())
SC = set(tuple(map(int, input().split())) for _ in range(M))

for i in range(10**N):
    num = str(i)
    if len(num) != N:
        continue
    chk = []
    for s, c in SC:
        if num[s-1] == str(c):
            chk.append(True)
        else:
            chk.append(False)
    if all(chk):
        print(num)
        exit()
print(-1)

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

int main(void) {
  int n, d;
  cin >> n >> d;
  
  int ans = n / (d * 2 + 1);
  if(n % (d * 2 + 1) != 0) {
    ans++;
  }

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

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int a,h,m,m1,s;
    scanf("%d%d%d",&a,&m,&h);
    if(a<m && m<h)printf("%d %d %d\n",a,m,h);
    if(a<h && h<m)printf("%d %d %d\n",a,h,m);
    if(m<a && a<h)printf("%d %d %d\n",m,a,h);
    if(m<h && h<a)printf("%d %d %d\n",m,h,a);
    if(h<m && m<a)printf("%d %d %d\n",h,m,a);
    if(h<a && a<m)printf("%d %d %d\n",h,a,m);
    if(h==a && h>m)printf("%d %d %d\n",m,a,h);
    if(h==a && h<m)printf("%d %d %d\n",h,a,m);
    if(m==a && h<m)printf("%d %d %d\n",h,a,m);
    if(m==a && h>m)printf("%d %d %d\n",m,a,h);
    if(h==m && h>a)printf("%d %d %d\n",a,h,m);
    if(h==m && h<a)printf("%d %d %d\n",h,m,a);
    return 0;
}



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

bool is_triangle(int a, int b, int c) {
  // a <= b <= c
  if (a == b || b == c) {
    return false;
  } 
  if (a + b > c) {
    return true;
  } 
  return false;
}

int main() {
  int N;
  cin >> N;
  vector<int> L(N);
  for (int i = 0; i < N; i++) {
    cin >> L[i];
  }
  sort(L.begin(), L.end());
  
  int ans = 0;
  for (int i = 0; i < N - 2; i++) {
    for (int j = i + 1; j < N - 1; j++) {
      for (int k = j + 1; k < N; k++) {
        if (is_triangle(L[i], L[j], L[k])) {
          ans++;
        }
      }
    }
  }
  cout << ans;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  ll x;
  cin>>x;
  bool ans = false;
  ll a = x / 100;
  ll b = x % 100;
  if (b <= 5 * a){
    ans = true;
  }
  if(ans){
    print(1);
  }
  else{
    print(0);
  }
}


Measured memory_bytes: 3532
#include <iostream>
using namespace std;
int a1, a2, b1, b2;
int main(){
	cin >> a1 >> a2 >> b1 >> b2;
	if (a2 <= b1 || a1 >= b2) cout << "0";
	else if (b1 >= a1 && b2 <= a2) cout << b2 - b1;
	else if (b1 <= a1 && b2 >= a2) cout << a2 - a1;
	else if (b1 > a1) cout << a2 - b1;
	else cout << b2 - a1;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
using Graph = vector<vector<int>>;
using Graphl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a)  (a).rbegin(),(a).rend()
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; }
template<class T> void PrintVector(const vector<T> &vec) {for (auto val : vec) cout << val << " "; cout << endl;}
const long long INF = 1LL << 60;
const long long minusINF = -(1LL << 40);
const int MOD = 1000000007;
const double PI = acos(-1); //3.14~
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main()
{
    int n, m; cin >> n >> m;
    Graphl a(n);
    vector<int> p(m), y(m);
    rep(i, m)
    {
        cin >> p[i] >> y[i]; --p[i];
        a[p[i]].push_back(y[i]);
    }

    for (auto &v : a)
    {
        sort(ALL(v));
        v.erase(unique(ALL(v)), v.end());
    }

    rep(i, m)
    {
        int index = lower_bound(a[p[i]].begin(), a[p[i]].end(), y[i]) - a[p[i]].begin();
        printf("%06d%06d\n", p[i] + 1, index + 1);
    }
}

Measured memory_bytes: 7808
n=int(input())
h=list(map(int,input().split()))
dp=[0]*n
dp[1]=abs(h[0]-h[1])
for i in range(n-2):
    dp[i+2]=min(dp[i+1]+abs(h[i+2]-h[i+1]),dp[i]+abs(h[i]-h[i+2]))
print(dp[n-1])

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

int main() {
    int H1, M1, H2, M2, K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;

    cout << (H2-H1)*60 + (M2-M1) - K << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <functional>
#include <set>
#include <numeric>
#define ll long long int
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main() {
	ll N, nx, e, ecnt, a, con = 0;

	cin >> N;
	nx = N;

	if (N % 10 == 3){
		cout << "bon" << endl;
		return 0;
	}
	else if ((N % 10 == 0) || (N % 10 == 1) || (N % 10 == 6) || (N % 10 == 8)){
		cout << "pon" << endl;
		return 0;
	}

	cout << "hon" << endl;
	return 0;
}

Measured memory_bytes: 3620
#include<iostream>
using namespace std;
int main(){
    int H;
    cin>>H;
    int T[H];
    for(int i=0;i<H;i++){
        cin>>T[i];
    }
    for(int i=1;i<H+1;i++){
        cout<<"node "<<i<<": key = "<<T[i-1]<<", ";
        if(i>1){
            cout<<"parent key = "<<T[i/2-1]<<", ";
        }
        if(i*2-1<H){
            cout<<"left key = "<<T[i*2-1]<<", ";
        }
        if(i*2<H){
            cout<<"right key = "<<T[i*2]<<", ";
        }cout<<endl;
    }return 0;
}


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

int H, W;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> H >> W;
    string str;
    for(int i=0; i<H; i++){
        cin >> str;
        cout << str << endl;
        cout << str << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, 0, n){
        cin >> a[i];
        a[i]--;
    }
    vector<int> d(n);
    rep(i, 0, n){
        d[a[i]]++;
    }
    sort(all(d));
    reverse(all(d));
    int ans = 0;
    rep(i, k, n){
        ans += d[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define step(i,n) if(i==0)i+=(int)(n)
int main(void) {
	int h, w;
	cin >> h >> w;
	h += 2;
	w += 2;
	vector<string> s(h);
	rep(i, h-1) {
		if (i == 0)
			i++;
		cin >> s[i];
		s[i] = 'x' + s[i] + 'x';
	}
	rep(i, w) {
		s[0][i] = 'x';
		s[h - 1][i] = 'x';
	}
	rep(i, h) {
		rep(j, w) {
			if (s[i][j] == '.') {
				s[i][j] = '0';
				rep(k, 3) {
					rep(l, 3) {
                      	int hh = i - 1 + k, ww = j - 1 + l;
                      	if(hh < 0 || hh >= h || ww < 0 || ww >= w)continue;
						if (s[hh][ww] == '#') {
							(char)s[i][j]++;
						}
					}
				}
			}
		}
	}
	h--;
	w--;
	rep (i, h) {
		step(i, 1);
		rep(j, w) {
			step(j, 1);
			cout << s[i][j];
		}
		cout << endl;
	}
	return 0;
}


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

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define EPS 1e-8
#define DEB 0

/*
const int dx[] = {0,1,0,-1}; //u,r,d,l
const int dy[] = {-1,0,1,0};
*/
const int dx[] = {1,0,-1,0}; //r,d,l,u
const int dy[] = {0,1,0,-1};

int w,h,sx,sy,home,last;
int field[16][16];
int num[16][16];

class state{
public:
  char x,y;
  int s;
  state(char _x, char _y, int _s){
    x = _x;
    y = _y;
    s = _s;
  }
  
  bool operator<(const state& a)const{
    if( s==a.s ){
      if( x==a.x ) return y<a.y;
      else         return x<a.x;
    }else{
      return s<a.s;
    }
    /*
    if( x==a.x ){
      if( y==a.y ) return s<a.s;
      else         return y<a.y;
    }else{
      return x<a.x;
    }
    */
  }
  
};

int numofbits(int bits) {
  bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
  bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
  bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
  bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
  return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}



map<state,int> msi;

bool isgoal(int s){
  return (((last&s)) == last);
}
bool inside(int x, int y){
  return (x<0 || y<0 || x>=w || y>=h);
}


int dfs(int x, int y, int s){
  if( (1<<home)-1 == s ){ //âÎÉßêé
    return 1;
  }
  if( isgoal(s) ){ //³ïÉßé½ßÌÆðÁïµ½©Ç¤©
    return 0;
  }
  if( msi.count(state(x,y,s)) ){ //ùÉÊÁ½óÔ
    return msi[state(x,y,s)];
  }
  
  int ret = 0;
  rep(k,4){
    for(int i=1; i<20; i++){
      int tx = x + dx[k]*i;
      int ty = y + dy[k]*i;
      if( inside(tx,ty) ) break;
      if( field[ty][tx]==1 ){
	field[ty][tx] = 0;
	ret += dfs(tx,ty,s|(1<<num[ty][tx]));
	field[ty][tx] = 1;
	break;
      }
    }
  }
  msi[state(x,y,s)] = ret;
  return ret;
}

int main(){

  while(scanf("%d%d",&w,&h),w|h){
    msi.clear();
    memset(num,-1,sizeof(num));
    home = last = 0;
    rep(i,h){
      rep(j,w){
	scanf("%d",&field[i][j]);
	if( field[i][j]==2 ){
	  sx = j;
	  sy = i;
	}
	if( field[i][j]==1 ){
	  num[i][j] = home;
	  home++;
	}
      }
    }

    //last homes
    rep(k,4){
      for(int i=1; i<20; i++){
	int tx = sx + dx[k]*i;
	int ty = sy + dy[k]*i;
	if( inside(tx,ty) )break;
	if( field[ty][tx]==1 ){
	  last |= (1<<num[ty][tx]);
	}
      }
    }

    printf("%d\n",dfs(sx,sy,0));
  }
  

  return 0;
}

Measured memory_bytes: 32000
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

const int mod = 1e9 + 7;

vector<long long> factorial;

long long mod_pow(long long a, long long p) {
	vector<long long> vals = {a};
	vector<long long> pow2s = {1};

	while (pow2s.back() < p) {
		long long val = vals.back() * vals.back() % mod;
		vals.emplace_back(val);
		pow2s.emplace_back(pow2s.back() << 1);

	}


	long long ret = 1;
	long long p2 = p;
	for (int i = vals.size() - 1; i >= 0; i--) {
		if (p2 >= pow2s[i]) {
			p2 -= pow2s[i];
			ret = (ret * vals[i]) % mod;
		}
	}

	return ret;
}

long long mod_combi(int n, int k) {
	long long x = factorial[n];
	long long y = factorial[k] * factorial[n-k] % mod;

	y = mod_pow(y, mod - 2);

	long long ret = x * y % mod;

	return ret;
}

int calc(int ball, int partition) {
	// printf("calc %d %d\n", ball, partition);
	return mod_combi(ball + partition, ball);
}

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

	int brue = k;
	int red = n - k;

	factorial.assign(4001, 1);
	for (int i = 1; i < factorial.size(); i++) {
		factorial[i] = factorial[i - 1] * i % mod;
	}


	vector<int> ans(k + 1, 0);
	for (int i = 1; i <= k; i++) {
		int rest_blue = k - i;
		int rest_red = red - (i - 1);

		if (rest_red < 0) {
			break;
		}

		int patition_blue = i;
		int patition_red = i + 1;

		ans[i] = 1LL * calc(rest_blue, patition_blue - 1) * calc(rest_red, patition_red - 1) % mod;
		// printf("ans [%d] %d\n", i, ans[i]);
	}

	for (int i = 1; i <= k; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 256
function Main(s) {
  var s = s.split("\n");
  var n = s[0]*1;
  var h = s[1].split(" ").map(e => e*1);
  var dp = new Array(n);
  dp[0] = 0;
  for(var i = 1; i < n; i++) {  
    if (i >= 2) {
      dp[i] = Math.min(dp[i - 1] + Math.abs(h[i - 1] - h[i]), dp[i - 2] + Math.abs(h[i - 2] - h[i]))
    } else {
      dp[i] = Math.abs(h[i - 1] - h[i]);
    }
  }
  console.log(dp[dp.length - 1]);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 27584
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        E solver = new E();
        solver.solve(1, in, out);
        out.close();
    }

    static class E {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            Set<Integer>[] e = new Set[n];
            for (int i = 0; i < n; i++) {
                e[i] = new HashSet<>();
            }

            for (int i = 0; i < n - 1; i++) {
                int a = in.nextInt();
                int b = in.nextInt();
                e[a].add(b);
                e[b].add(a);
            }

            ArrayList<Integer> deg2 = new ArrayList<>();
            ArrayList<Integer> deg1 = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (e[i].size() == 1) {
                    deg1.add(i);
                }
                if (e[i].size() == 2) {
                    deg2.add(i);
                }
            }

            for (int i = 0; i < deg2.size(); i++) {
                int x = deg2.get(i);
                int y = e[x].iterator().next();
                e[x].remove(y);
                int z = e[x].iterator().next();
                e[x].remove(z);
                e[y].remove(x);
                e[z].remove(x);
                e[y].add(z);
                e[z].add(y);
            }

            if (n == 2 + deg2.size()) {
                out.println(1);
                return;
            }

            int[] neiL = new int[n];
            for (int i = 0; i < n; i++) {
                if (e[i].size() == 0) {
                    continue;
                }
                if (e[i].size() == 1) {
                    int x = e[i].iterator().next();
                    neiL[x] += 1;
                }
            }

            int ans = 0;
            for (int i = 0; i < n; i++) {
                if (neiL[i] > 0) {
                    ans += neiL[i] - 1;
                }
            }
            out.println(ans);

        }

    }
}



Measured memory_bytes: 117804
n,m = map(int,input().split())

abl = []
for _ in range(m):
    a,b = map(int,input().split())
    abl.append((a,b))
    
abl = sorted(abl)

ans = 0
tail = 0
for a,b in abl:
    if tail <= a:
        ans += 1
        tail = b
    else:
        if b < tail:
            tail = b
            
print(ans)
    



Measured memory_bytes: 54232
#include "iostream"
using namespace std;

int main(){
	int d, n;
	cin >> d >> n;
	if (d == 0) {
		if (n != 100)
			cout << n << endl;
		else cout << 101 << endl;
	}
	else if (d == 1) {
		if (n != 100)
			cout << n * 100 << endl;
		else cout << 10100 << endl;
	}
	else {
		if (n != 100)
			cout << n * 10000 << endl;
		else cout << 1010000 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
def f_polynomal_construction(P, A):
    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    combination = Combination(P - 1, P)
    comb = [combination.combination(P - 1, i) for i in range(P)]

    ans = [0] * P
    for j, a in enumerate(A):
        if a == 0:
            continue
        # 1-(x-j)^{p-1} = 1 - \sum_{k=0}^{p-1} comb(p-1, p-k-1) * x^{p-k-1} * (-j)^k
        # なので、定数項に1を足し、x^k の係数から各々引く
        # pow(-j, k, P) としたいが、時間がかかるので tmp に掛けていくことにする
        ans[0] += 1
        tmp = 1
        for k in range(P):
            index = P - k - 1
            if k > 0:
                tmp *= (-j)
                tmp %= P
            ans[index] -= comb[index] * tmp
            ans[index] %= P
    return ' '.join(map(str, ans))

P = int(input())
A = [int(i) for i in input().split()]
print(f_polynomal_construction(P, A))

Measured memory_bytes: 41840
fn main() {
    let mut input_iter = read_line_as_vector::<f64>().into_iter();
    let a = input_iter.next().unwrap();
    let b = input_iter.next().unwrap();
    let x = input_iter.next().unwrap();

    let angle = if x >= a*a*b/2.0 {
        let rad = (2.0*b/a - 2.0*x/(a*a*a)).atan();
        180.0 * (rad / std::f64::consts::PI)
    } else {
        let rad = (2.0*x/(a*b*b)).atan();
        90.0 - 180.0 * (rad / std::f64::consts::PI)
    };
    println!("{}", angle);
}

fn read_line_as_vector<T: std::str::FromStr>() -> Vec<T> {
    let mut input = String::new();
    let res = std::io::stdin().read_line(&mut input);
    if let Err(error) = res {
        panic!("io error at stdin.read_line: {}", error);
    };
    match input.trim().split_whitespace().map(|x| x.parse()).collect::<Result<Vec<T>, _>>() {
        Ok(vec) => vec,
        _ => panic!("error while parsing input: {}", input)
    }
}


Measured memory_bytes: 2876
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> mat;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define rep(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define mset(a,x) memset(a,x,sizeof(a))
#define FASTIO cin.tie(0),ios::sync_with_stdio(0)

string s1 = "UNRESTORABLE";

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

    int n = s.size(), m = t.size();
    if (n < m) {
        cout << s1 << endl;
        return 0;
    }

    for (int i = n - m; i >= 0; i--) {
        bool can = true;
        rep(j, m) {
            can &= s[i + j] == '?' || s[i + j] == t[j];
        }
        if (!can) continue;

        rep(j, n) {
            if (i <= j && j < i + m)
                cout << t[j - i];
            else if (s[j] == '?')
                cout << "a";
            else
                cout << s[j];
        }
        puts("");
        return 0;
    }

    cout << s1 << endl;


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
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<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;}
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N;
        cin >> N;
        ll ans = N / 1000;
        if (N % 1000 != 0) ans += 1;
        cout << ans*1000 - N << endl;
}

Measured memory_bytes: 3620
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,d = map(int,readline().split())
ans = 0

for i in range(n):
    a,b = map(int,readline().split())
    if d >= (a**2 + b**2)**0.5:
        ans += 1

print(ans)

Measured memory_bytes: 69220
#include<iostream>
#include <algorithm>
#include<string>

using namespace std;
int main() {
    string s= "", c= "",a= "",b= "",x= "",y = "";
    string ans = "Yes";
    cin >> s;
    c = s;
    reverse(s.begin(), s.end());
    if (c != s)ans = "No";

    // cout<<c<<" "<<s<<endl;

    for (int i = 0; i < (s.size()-1)/2; i++)a += s[i];
    b = a;
    reverse(b.begin(), b.end());
    if (a != b)ans = "No";

        // cout<<a<<" "<<b<<endl;

    for (int i = (s.size()-1+3)/2; i < s.size(); i++)x += s[i];
    y = x;
    reverse(y.begin(), y.end());
    if (x != y)ans = "No";
    // cout<<x<<" "<<y<<endl;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    char N[3];
    int i = 0, j = 0;
    for (i = 0; i < 3; i++) {
        scanf(" %c", &N[i]);
        if (N[i] == '1')
            N[i] = '9';
        else if (N[i] == '9')
            N[i] = '1';
    }
    
    for (j = 0; j < 3; j++) {
        printf("%c", N[j]);
    }
    
    return 0;
}

Measured memory_bytes: 128
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.bigint, std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

void chmin(T)(ref T x, T y) { x = min(x, y); } void chmax(T)(ref T x, T y) { x = max(x, y); }
bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
T lcm(T)(T x, T y) { return x * (y / gcd(x, y)); }

//long mod = 10^^9 + 7;
long mod = 998_244_353;
//long mod = 1_000_003;
void moda(T)(ref T x, T y) { x = (x + y) % mod; }
void mods(T)(ref T x, T y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(T)(ref T x, T y) { x = (x * y) % mod; }
void modpow(T)(ref T x, T y) { if (!y) { x = 1; return; } auto t = x; x.modpow(y>>1); x.modm(x); if (y&1) x.modm(t); }
void modd(T)(ref T x, T y) { y.modpow(mod - 2); x.modm(y); }

void main()
{
	auto S = RD!string;

	writeln(S[0..3]);
	stdout.flush;
	debug readln;
}


Measured memory_bytes: 2708
#include <iostream>
#include <vector>
#include <cstdio>

#define MAX_V 200005

using namespace std;

vector<int> tree[MAX_V];
long long cost[MAX_V];

void dfs(int cur_v, int par_v) {
  if (par_v != -1) { cost[cur_v] += cost[par_v]; }
  for (int i = 0; i < tree[cur_v].size(); i++) {
    int e = tree[cur_v][i];
    if (e == par_v) { continue; }
    dfs(e, cur_v);
  }
}
 
int main() {
  int N, Q;
  scanf("%d %d", &N, &Q);

  for (int i = 0; i < N-1; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--, b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }

  for (int i = 0; i < Q; i++) {
    int p, x;
    scanf("%d %d", &p, &x);
    // 0-index にしたいので, decriment
    cost[p-1] += x;
  }

  dfs(0, -1);

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

Measured memory_bytes: 24320
import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


class FenwickTree:
    def __init__(self, n):
        self._n = n
        self._a = [0] * n

    def add(self, i, x):
        i += 1
        while i <= self._n:
            self._a[i - 1] += x
            i += i & -i

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

    def _sum(self, r):
        s = 0
        while r > 0:
            s += self._a[r - 1]
            r -= r & -r
        return s


def main():
    n, q = map(int, read().split())
    fw = FenwickTree(n)
    for i, ai in enumerate(map(int, read().split())):
        fw.add(i, ai)
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            fw.add(query[1], query[2])
        else:
            print(fw.sum(query[1], query[2]))


if __name__ == '__main__':
    main()


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

int main(void)
{
    int A, B, N;
    string S;
    cin >> N >> A >> B;
    cin >> S;
    string c;
    int p = 0;
    int b = 0;
    //char c;

    for (int i=0; i < S.size(); i++){
        //c = S.at(i);
        if(S.at(i) == 'a'){
            if(p < A+B){
            cout << "Yes" << endl;
            p++;
            }else{
                cout << "No" << endl;
            }
    }else if(S.at(i) == 'b'){ 
         if(p < A+B && b < B){
            cout << "Yes" << endl;
            p++;
            b++;
         }else{
            cout << "No" << endl;
         }
    }else{
            cout << "No" << endl;
    }

    }
}


Measured memory_bytes: 3720
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const long long mod = 1000000007;
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int x,y,z;
    cin>>x>>y>>z;
    ll ans=0;
    for(int i=1;;i++){
        if(y*i+z*i+z>x){
            cout<<i-1<<endl;
            break;
        }
        else if(y*i+z*i+z>=x){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio std::ios_base::sync_with_stdio(false), std::cout.tie(0), std::cin.tie(0);
#define N 100007
#define mxx INT_MAX

typedef long long ll;

int main(){
	int num1,num2;
	std::cin>>num1>>num2;
	if(num2>=num1)std::cout<<"unsafe";
	else std::cout<<"safe";



}


Measured memory_bytes: 3636
using System;
using System.Collections.Generic;
class Program{
	static long[] h;
	static List<int[]>[] li;
	static string ans="Yes";
	static void Main(){
		int[] s=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
		h=new long[s[0]+1];
		li=new List<int[]>[s[0]+1];
		for(int i=1;i<=s[0];i++){
			h[i]=long.MinValue;
			li[i]=new List<int[]>();
		}
		for(int i=0;i<s[1];i++){
			int[] q=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
			li[q[0]].Add(new int[]{q[1],q[2]});
			li[q[1]].Add(new int[]{q[0],-q[2]});
		}
		for(int i=1;i<=s[0]&&ans=="Yes";i++){
			if(h[i]==long.MinValue){
				h[i]=0;
				fu(i);
			}
		}
		Console.WriteLine("{0}",ans);
	}
	static void fu(int a){
		for(int i=0;i<li[a].Count&&ans=="Yes";i++){
			if(h[li[a][i][0]]==long.MinValue){
				h[li[a][i][0]]=h[a]+li[a][i][1];
				fu(li[a][i][0]);
			}
			else if(h[li[a][i][0]]!=h[a]+li[a][i][1]){
				ans="No";
				break;
			}
		}
	}
}

Measured memory_bytes: 53012
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define vi vector <int>
#define pf push_front
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define el "\n"
#define all(v) v.begin(),v.end()
#define ull unsigned long long
#define int long long
#define MAXN   10000001
const int no_of_chars = 256;
const int mod = 1e9 + 7;
int i, j;
int fastpow(int x, int y)
{
	int res = 1;
	x %= mod;
	while (y)
	{
		if (y & 1)
			res = (res * x) % mod;
		x = (x * x) % mod;
		y = (y >> 1);
	}
	return res;
}

int prod(int x, int y)
{
	int res = 0;
	x %= mod;
	while (y)
	{
		if (y & 1)
			res = (res + x) % mod;
		x = (x * 2) % mod;
		y = y >> 1;
	}
	return res;
}

int32_t main()
{
	FAST;

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int t = 1;
	// cin >> t;
	while (t--) {
		int n;
		cin >> n;
		string s;
		cin >> s;
		if (s.length() > n) {
			for (i = 0; i < n; i++)
				cout << s[i];
			cout << "...";
			cout << el;
		}
		else
			cout << s << el;
	}
	return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<iostream>
#include<cmath>
#include<math.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
const double PI=M_PI;
signed main(){
    double a,b;cin>>a>>b;
    double h,m;cin>>h>>m;
    double c=abs(2*PI*((h*60.0+m)/720-m/60.0));
    if(c>PI)c=2*PI-c;
    cout<<fixed<<setprecision(12)<<sqrt(a*a+b*b-a*b*2*cos(c))<<endl;
}

Measured memory_bytes: 4288
#include<iostream>
#include<vector>
#define MAXN 100005
using namespace std;

int h[MAXN];
vector<int> edge[MAXN];

int main(void)
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>h[i];
    for(int i=0;i<m;++i){
        int a,b; cin>>a>>b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    int ans = 0;
    for(int i=1;i<=n;++i){
        bool flag = true;
        int len = edge[i].size();
        for(int j=0;j<len;++j){
            if(h[edge[i][j]] >= h[i]){
                flag = false;
                break;
            }
        }
        if(flag) ++ans;
    }
    cout<<ans;
    return 0;
}

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

long long mp[20000];

int main()
{


        long long n,m,a,b,c,d,e,f,g,h,p,q,r,fr,sc,tr,sz,tz,i,j,k,mx=LLONG_MIN,mn=LLONG_MAX;
        long long x=0,y=0,cnt=0,res=0,ttl=0,ans=0,sum=0; long long flg=0,flag=1,na=0,as=1;
        vector<long long>u,v,w; vector< pair<long long,long long> >vct; vector<string>vst;
        set<long long>st,nt,tt; map<long long,long long>nq,qr; string str,ttr,ntr;

        scanf("%lld",&n);

        for(i=1;i<=101;i++)
        {
            for(j=1;j<=101;j++)
            {
                for(k=1;k<=101;k++)
                {

                    fr=(i*i)+(j*j)+(k*k)+(i*j)+(j*k)+(k*i);
                    if(fr<=11000)
                    {
                        mp[fr]++;
                    }

                }

            }

        }




        for(i=1;i<=n;i++)
        {
            printf("%lld\n",mp[i]);
        }





    return 0;
}





Measured memory_bytes: 3840
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;

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

long long int a[3][100001];

struct mise {
	int number;
	string name;
	int value;
};

bool biggerthan(mise a, mise b) {
	if (a.name != b.name)  return a.name < b.name;
	return a.value > b.value;
}

int main() {
	int n;
	cin >> n;
	vector<mise> a(n);
	string name;
	int value;
	for (int i = 0; i < n; i++) {
		cin >> name >> value;
		a.at(i).name = name;
		a.at(i).number = i + 1;
		a.at(i).value = value;
	}
	sort(a.begin(), a.end(), biggerthan);
	for (int i = 0; i < n; i++) {
		mise tmp = a.at(i);
		cout << tmp.number << endl;
	}
	
}


Measured memory_bytes: 256
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def dfs(N):
    """
    param N:文字列の長さ

    """
    result = []
    stack = [("a", 1)]
    
    while stack:
        s, max_ = stack.pop()
        if len(s) == N:
            result.append(s)
            continue
        else:
            for i in range(max_+1):
                stack.append((s + chr(97+i), max(max_, i+1)))
    
    return result


def main():
    N = int(readline())

    ans = dfs(N)
    print("\n".join(ans[::-1]))
            

if __name__ == "__main__":
    main()


Measured memory_bytes: 15164
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    sl = []
    for _ in range(n):
        s = list(input())
        s.sort()

        sl.append(''.join(s))

    counter = Counter(sl)
    ans = 0
    for s, c in counter.items():
        if c > 1:
            ptn = c * (c-1) // 2
            ans += ptn
    print(ans)

if __name__ == '__main__':
    main()


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

using namespace std;

#define loop(i, n) for(int i = 0;i < int(n);i++)
#define rloop(i, n) for(int i = int(n);i >= 0;i--)
#define range(i, a, b) for(int i = int(a);i <= int(b);i++)
#define SZ(c) int(c.size())
#define ALL(c) c.begin(), c.end()
#define RALL(c) c.rbegin(), c.rend()
#define PI acos(-1)
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define sfi1(v) scanf("%d",&v)
#define sfi2(v1, v2) scanf("%d %d",&v1,&v2)
#define sfi3(v1, v2, v3) scanf("%d %d %d",&v1,&v2,&v3)
#define sfll1(v) scanf("%I64d",&v);
#define sfll2(v1, v2) scanf("%I64d %I64d",&v1,&v2)
#define sfll3(v1, v2, v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
#define endl '\n'

typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 5;
pii arr[N];
int add[N];
int n, d, a;

int main() {

#ifndef ONLINE_JUDGE
    //freopen("in.in", "r", stdin);
    //freopen("out.in", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll ans = 0;
    int bomb = 0;
    cin >> n >> d >> a;
    loop(i, n)cin >> arr[i].fr >> arr[i].sc;
    sort(arr, arr + n);

    loop(i, n) {
        int need = (arr[i].sc + a - 1) / a;
        bomb += add[i];
        if (need <= bomb)continue;
        int extra = need - bomb;
        int idx = upper_bound(arr, arr + n, make_pair(arr[i].first + d + d + 1, -1)) - arr;
        add[idx] -= extra;
        ans += extra;
        bomb += extra;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define int ll
#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)3e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

void solve() {
    int k;
    cin>>k;
    int ans = 0;
    rep(i, 1, k) {
        rep(j, 1, k) {
            rep(ii, 1, k) {
                ans += __gcd(__gcd(i, j), ii);
            }
        }
    }
    cout<<ans;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int t = 1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define lld long long
#define pb push_back
#define mk make_pair
#define MAX (lld)1e18+7
#define lim (lld)1e9+7
#define MAX2 (int)2e5+9
#define ff first
#define ss second
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const lld mod=lim;

lld power(lld x, lld y, lld p)  
{   lld res = 1;     x = x % p; if (x == 0) return 0;  
  
    while (y > 0)  
    { if (y & 1) res = (res*x) % p;  y = y>>1; x = (x*x) % p;   }  
    return res;  } 


int extend_gcd(int a, int b, int& x, int& y) {
    if (b == 0) { x = 1;y = 0;return a;}
    int x1, y1;
    int d = extend_gcd(b, a % b, x1, y1);
    x = y1; y = x1 - y1 * (a / b);return d;	}

int rowNum[]={-1,0,0,1};
int colNum[]={0,-1,1,0};

int main()
{
	fastio
	int n,k;
	cin>>n>>k;

	std::vector<int> v(n+1);

	for(int i=1;i<=n;i++)
		cin>>v[i];

	for(int i=k+1;i<=n;i++)
	{	
		if(v[i]>v[i-k])
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
}

Measured memory_bytes: 3984
#include <stdio.h>
#include <math.h>

	int mod=1000000007;
int fanc(long long a,int n){
return n?(fanc((a*a)%mod,n/2)*(n%2?a:1))%mod:1;
}
int main(void){
	int a,b,N,K,count;
	long long sum;
	long long del[100001];
	sum = 0;
	scanf("%d %d",&K,&N);
	for(a=N;0<a;a--){
		count=N/a;
		del[a]=fanc(count,K);
		if(1<count)
			for(b=2;b<=count;b++)
				del[a]=(del[a]+mod-del[a*b])%mod;
        	sum=(sum+a*del[a])%mod;
 }
    printf ("%lld",sum);
    return 0;
}

Measured memory_bytes: 2444
n = int(input())
s = input()

cnt_left = 0
cnt_right = s[1:].count('E')
ret = cnt_left + cnt_right

for i in range(1, n):
    if s[i] == 'E':
        cnt_right -= 1
    if s[i-1] == 'W':
        cnt_left += 1
    ret = min(ret, cnt_left + cnt_right)

print(ret)


Measured memory_bytes: 42692
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m=0;cin>>n;
  vector<int>a(n),b(n);
  for(int i=0;i<n;i++){
    cin>>a.at(i);
    b.at(i)=0;
  }
  for(int j=n-1;j>=0;j--){
    if(j>n/2-1)b.at(j)=a.at(j);
    else{
      int s=n/(j+1),t=0;
      for(int k=1;k<s;k++){
        t+=b.at((j+1)*(k+1)-1);
      }
      t=t%2;
      if(t!=a.at(j))b.at(j)=1;
    }
    m+=b.at(j);
  }
  cout<<m<<endl;
  for(int l=0;l<n;l++){
    if(b.at(l)==1)cout<<l+1<<" ";
  }
  cout<<endl;
}

Measured memory_bytes: 2432
#include <iostream>

using namespace std;

int main(){
    int N;
    cin >> N;
    int max_four, max_seven;
    bool flag = false;

    max_four = N/4 + 1;
    max_seven = N/7 + 1;

    for(int i=0; i < max_four; i++){
        for(int j=0; j < max_seven; j++){
            if(N == 4*i + 7*j){
                flag = true;
                break;
            }
        }
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vll vector<ll>
#define pb push_back
#define x first
#define y second
#define pii pair<int,int>

const int mod = 1e9+7;

int main()
{
	ll N,A,B;
	cin>>N>>A>>B;
	cout<<(N)/(A+B) * A + min(A,N%(A+B));
}

Measured memory_bytes: 256