akhauriyash/Code-Regression huggingface dataset:
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;

const int MAX_N = 100,MAX_V=1e3;

int N,W;
vi w,v;
vector<vi> dp;

signed main(){

    in(N,W);
    resz(N,w,v);
    rep(i,N){
        in(w[i],v[i]);
    }
    dp.resize(N+10,vi(MAX_N*MAX_V+10,INF));
    dp[0][0]=0;
    rep(i,N){
        rep(j,MAX_N*MAX_V+1){
            if(j<v[i]){
                dp[i+1][j]=dp[i][j];
            }else{
                dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);
            }
        }
    }
    int res=0;
    rep(i,MAX_N*MAX_V+1){
        if(dp[N][i]<=W) res=i;
    }
    out(res);

    return 0;
}


Measured memory_bytes: 87296
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
  int n,k;
  char s[16],ch;
  scanf("%d",&n);
  scanf("%s",s);
  scanf("%d",&k);
  
  ch = s[k-1];
  k = strlen(s);
  
  for (auto i = 0 ; i < k ; ++i)
    putchar(s[i] == ch ? s[i] : '*');
  return 0;
}


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

int main() {
	// your code goes here
	int n,m;
	cin>>n>>m;
	
	vector<int>a(n,-1);
	int f=0;
	for(int i=0;i<m;i++)
	{
	    int s,c;
	    cin>>s>>c;
	    s--;
	    if(a[s]==-1)
	    a[s]=c;
	    else if(c==a[s])
	    continue;
	    else
	    f=1;
	    
	}
	if(f)
	cout<<-1;
	else if(n>1 && a[0]==0)
	cout<<-1;
	else if(m==0 && n==1)
	cout<<0;
	else
	{
	    if(a[0]==-1)
	    a[0]=1;
	    for(int i=1;i<n;i++)
	    {
	        if(a[i]==-1)
	        a[i]=0;
	    }
	    int ans=0;
	    for(int i=0;i<n;i++)
	    ans=ans*10+a[i];
	    cout<<ans;
	}
	

	
	return 0;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define int long long 

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
  dp[i][j]
    i個目までで
    j : どの状態か
    0=散歩前(コストa[i])
    1=スタートからいくつか(奇数はコスト)
    2=あいだ（偶数はコスト)
    3=ゴールからいくつか(奇数はコスト)
    4=散歩後(コストa[i])
    のときのコストの最小値
*/

ll dp[200001][5];

signed main()
{
  int n;
  cin >> n;

  vi a(n);
  rep(i, n) cin >> a[i];

  rep(i, 200001) rep(j, 5) dp[i][j] = i==0 ? 0 : linf;

  rep(i, n){
    int c = a[i], mindp = dp[i][0];
    dp[i+1][0] = min(dp[i+1][0], mindp + c);

    c = a[i] == 0 ? 2 : a[i]%2;
    mindp = min(mindp, dp[i][1]);
    dp[i+1][1] = min(dp[i+1][1], mindp + c);

    c = a[i]%2 == 0;
    mindp = min(mindp, dp[i][2]);
    dp[i+1][2] = min(dp[i+1][2], mindp + c);

    c = a[i] == 0 ? 2 : a[i]%2;
    mindp = min(mindp, dp[i][3]);
    dp[i+1][3] = min(dp[i+1][3], mindp + c);

    c = a[i];
    mindp = min(mindp, dp[i][4]);
    dp[i+1][4] = min(dp[i+1][4], mindp + c);
  }

  ll ans = linf;
  rep(i, 5){
    ans = min(ans, dp[n][i]);
//    cout << dp[n][i] << endl;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 9600
#include <cstring>
#include<cstdio>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
long long a,n;
int main()
{
	cin>>n;
	a=1;
	for(long long i=1;i<=n;i++)
	{
		a=a*i%1000000007;
	}
	cout<<a<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define SQR(x) ((x)*(x))

int cmp(const void *a,const void *b){
	return *(double *)a-*(double *)b;
}

int main(void){
	int n,r,i;
	double c[3];
	while(1){
		for(i=0;i<3;i++){
			scanf("%lf",&c[i]);
		}
		if(!(c[0]+c[1]+c[2]))break;
		qsort(c,3,sizeof(double),cmp);
		scanf("%d",&n);
		while(n--){
			scanf("%d",&r);
			if(SQR(r)>SQR(c[0]/2)+SQR(c[1]/2))puts("OK");
			else puts("NA");
		}
	}
	return 0;
}

Measured memory_bytes: 616
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;

//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;}
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;}

ll f(ll x, int c, int d) {
    ll res = x;
    res -= x/c;
    res -= x/d;
    res += x/lcm(c,d);
    return res;
}

int main() {
    ll a, b;
    int c, d;
    cin >> a >> b >> c >> d;
    ll ans = f(b,c,d) - f(a-1,c,d);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
s_xy = set(xy)

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        p, q = xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]
        count = max(count, sum((x-p,y-q) in s_xy for x, y in s_xy))

print(n - count)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>


using namespace std;
using ll = long long int;

#define rep(i, n) for(ll i = 0; i < (n); i++)
#define MOD 998244353LL


ll pow(ll n, ll k) {
  ll r = 1;

  while (k > 0) {
    if (k % 2 == 1) {
      r = r * n % MOD;
    }
    n = n * n % MOD;
    k /= 2;
  }
  return r;
}

ll fac[3000000];

ll inv(ll x) {
  return pow(x, MOD - 2);
}


ll C(ll n, ll k) {
  if (k > 0) {
    return fac[n] * inv(fac[n - k]) % MOD * inv(fac[k]) % MOD;
  } else {
    return 1;
  }
}

void solve(ll n, ll m, ll k) {
  ll ans = 0;

  rep(i, k + 1) {
    ans += m * pow(m - 1, n - 1 - i) % MOD * C(n - 1, i) % MOD;
    ans %= MOD;
  }

  cout << ans << endl;
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  ll N, M, K;
  cin >> N >> M >> K;

  fac[0] = 1;
  ll f = 1;
  for (ll i = 1; i < 3000000; i++) {
    f *= i;
    f %= MOD;
    fac[i] = f;
  }

  solve(N, M, K);
  return 0;
}

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

int main()

{
    int A,B,C,D,E;

    scanf("%d%d",&A,&B);

    C=(A+B)/2;

    if(A>C){

        D=A-C;
    }
    else{

        D=C-A;
    }

    if(B>C){

        E=B-C;
    }
    else{

        E=C-B;
    }

    if(D==E){

        printf("%d",C);

    }

    else{

        printf("IMPOSSIBLE");
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll gcd(ll a, ll b) {
	return (b == 0 ? a : gcd(b, a % b));
}

ll n, a[110000], b[110000], s[110000], ans = 0;
int main() {
	cin >> n;
	REP(i, n) {
		cin >> s[i];

	}
	REP(i, n) {
		if (i == 0)a[0] = s[0];
		a[i + 1] = gcd(a[i], s[i]);
	}
	a[0] = 1;
	REPR(i, n - 1) {
		if (i == n - 1)b[i + 1] = s[n - 1];
		b[i] = gcd(b[i + 1], s[i]);
	}
	b[n] = 1;
	REP(i, n) {
		if (i == 0)ans = max(ans, b[i + 1]);
		else if (i == n - 1)ans = max(ans, a[i]);
		else ans = max(ans, gcd(a[i], b[i + 1]));
	}
	cout << ans << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll Mod = 998244353;
const int MAX = 5100000;
const double PI = 3.14159265358979;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i=0; i<N; i++) cin >> a[i];
  for (int i=0; i<N; i++) {
    if (a[i]%2!=0) {
      cout << "first" << endl;
      return 0;
    }
  }
  cout << "second" << endl;
  return 0;
}

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

int main(){
  int w,a,b;
  cin >> w >> a >> b;
  if(a+w<b){
    cout << b-a-w << endl;
  }else if(b+w<a){
    cout << a-b-w << endl;
  }else{
    cout << 0 << endl;
  }
}

Measured memory_bytes: 3612
#貪欲の手順がおかしかった
#同一ペアを組むのはそれ以下の数を除いた後
#editorial参照、さらに単純に0で区切ってn//2になる
n = int(input())
a = []
for _ in range(n):
    a_ = int(input())
    a.append(a_)
#print(a)
ans = 0
"""
for i in range(n-1):
    if a[i]&1:
        ans += a[i]//2
        a[i] = 1
    elif a[i] ==0:
        pass
    else:
        ans += a[i]//2-1
        a[i] = 2
print(a)
print(ans)
"""
for i in range(n-1):
    ans += a[i]//2
    a[i] -= (a[i]//2)*2
    ad = min(a[i],a[i+1])
    ans += ad
    a[i+1] -= ad
##この時点で最後まだ残っている
ans += a[n-1]//2
print(ans)

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

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

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

const ll INF = 1e13;
int main(){
  ll n,x;
  cin >> n >> x;
  VLL a(n);
  VLL b(n);
  rep(i,n){
    cin >> a[i];
    b[i] = a[i];
  }
  ll ans = INF;
  rep(k,n){// k回の操作内でスライムを作る場合の最小回数
    ll cost = x * k; //操作をするためのコスト
    rep(i,n) b[i] = min(b[i],a[(i-k+n)%n]);
    rep(i,n) cost += b[i];
    ans = min(ans,cost);
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
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; }
const ll MOD = 1e9+7;

int main(){
    ll X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;

    priority_queue<pair<ll, ll>> que;
    REP(i,A){
        ll a;
        cin >> a;
        que.push(make_pair(a, 0));
    }
    REP(i,B){
        ll a;
        cin >> a;
        que.push(make_pair(a, 1));
    }
    REP(i,C){
        ll a;
        cin >> a;
        que.push(make_pair(a, 2));
    }

    ll a = 0, b = 0, c = 0;
    ll ans = 0;
    while(1){
        auto p = que.top();
        que.pop();

        ll val = p.first;
        ll color = p.second;

        if(color == 0){
            if(a != X){
                a += 1;
                ans += val;
            }
        }
        else if(color == 1){
            if(b != Y){
                b += 1;
                ans += val;
            }
        }
        else{
            c += 1;
            ans += val;
        }

        if(a + b + c == X + Y)
            break;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 10092
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int lld;

const lld mod = 1e9+7;
const lld INF = 1e9;
const lld MAX = 1e9;

int main()
{
	lld n,m;
	cin >> n >> m;
	vector<lld> x(n),y(m);
	for(int i = 0; i < n; i++)
	{
		cin >> x[i];
		x[i] += MAX;
		x[i] %= mod;
	}
	for(int i = 0; i < m; i++)
	{
		cin >> y[i];
		y[i] += MAX;
		y[i] %= mod;
	}

	vector<lld> x_sum(n),y_sum(m);
	x_sum[0] = x[0];
	y_sum[0] = y[0];

	for(int i = 1; i < n; i++)
	{
		x_sum[i] = x_sum[i-1] + x[i];
		x_sum[i] %= mod;
	}
	for(int i = 1; i < m; i++)
	{
		y_sum[i] = y_sum[i-1] + y[i];
		y_sum[i] %= mod;
	}

	lld A=0,B=0;

	for(int i = 1; i < n; i++)
	{
		A += i*x[i] - x_sum[i-1];
		A %= mod;
	}
	for(int i = 1; i < m; i++)
	{
		B += i*y[i] - y_sum[i-1];
		B %= mod;
	}

	cout << (A*B)%mod << endl;

	return 0;
}

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

#define fi first
#define se second

const int N = 200200;
const int mod = 1e9 + 7;

using namespace std;

int main()
{
        ios_base::sync_with_stdio(0);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        int n, m;
        cin >> n >> m;
        long long res = 1;
        for(int i = 1; i <= n; i++) res *= i, res %= mod;
        for(int i = 1; i <= m; i++) res *= i, res %= mod;
        if(abs(n - m) > 1){
                res = 0;
        } else if(n == m){
                res *= 2;
                res %= mod;
        }
        cout << res << "\n";
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int n, k;
    cin >> n >> k;
    cout << n - k + 1 << endl;
    return 0;
}


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

ans = 0

for i in range(n-1):
    left = s[0:i]
    right = s[i:n]

    sleft = set([x for x in left])
    sright = set([x for x in right])

    tmp = len(sleft & sright)
    if tmp > ans:
        ans = tmp

print(ans)


Measured memory_bytes: 9184
n, k = gets.split.map(&:to_i)
array = Array.new(10**5 + 1, 0)
n.times do
  a, b = gets.split.map(&:to_i)
  array[a] += b
end

array.each_with_index do |b, a|
  k -= b
  if k <= 0
    puts a
    break
  end
end


Measured memory_bytes: 4604
#include<stdio.h>

int main(void){
int a,b,s,d;

while(scanf("%d %d",&a,&b)!=EOF){

s=a+b;
d=0;
while(!(s<1)){
  s=s/10;
  d++;
}
printf("%d\n",d);
}
return 0;
}

Measured memory_bytes: 600
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {


       // BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int arr[] = new int[n];

        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        int a = 0;
        int b = Math.abs(arr[1]-arr[0]);

        if(n==2){
            System.out.println(b);
            System.exit(0);
        }

        int c = 0;

        for(int i=2;i<n;i++) {
            c = Math.min(Math.abs(arr[i]-arr[i-1])+b, Math.abs(arr[i]-arr[i-2])+a);
            a = b;
            b = c;
        }

        System.out.println(c);
    }
}

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

int main(void)
{
  string s, t;
  int ans = 0;

  cin >> s >> t;

  for (int i = 0; i < s.size(); i++)
  {
    if (s[i] == t[i])
      ans++;
  }

  if (ans == s.size())
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


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

// DAME:
// TIPS: bを固定して考える。aを動かさなくても答えがでる。
int main() {
    int n, k;
    cin >> n >> k;
    ll ans = 0;
    if(k==0){
        ans = pow(n, 2);
        cout << ans << endl;
        return 0;
    }
    for(int i=k+1; i<=n; i++){
        ans += (ll)(i-k)*(n/i);
        if(n%i >= k){
            ans += n%i-k+1;
        }
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct UnionFind
{
    //自身が親であれば、その集合に属する頂点数に-1を掛けたもの
    //そうでなければ親のid
    vector<int> r;

    UnionFind(int N)
    {
        r = vector<int>(N, -1);
    }

    int root(int x)
    {
        if (r[x] < 0)
            return x;
        return r[x] = root(r[x]);
    }

    bool unite(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (r[x] > r[y])
            swap(x, y);
        r[x] += r[y];
        r[y] = x;
        return true;
    }

    int size(int x)
    {
        return -r[root(x)];
    }
    bool same(int x, int y){ // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
int main(){
    int N,M,i,p,q,a;
    cin >> N >> M;
    UnionFind tree(N + 10);
    for (i = 0; i < M; i++){
        cin >> p >> q;
        tree.unite(p,q);
    }
    a = 0;
    vector<bool> sirabe(N + 10,false);
    for(p = 1;p <= N;p++){
      a = max(a,tree.size(p));
    }
    cout << a << endl;
}

Measured memory_bytes: 4036
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

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

	int n, k; cin >> n >> k;
	string s; cin >> s;

	int p = 1;
	FOR_LT(i, 0, s.size() - 1) {
		if (s[i] != s[i + 1]) p++;
	}

	cout << min(n - 1, n - p + 2 * k) << endl;
	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

int sum(int arg1, int arg2) {
  return arg1 + arg2;
}

int sub(int arg1, int arg2) {
  return arg1 - arg2;
}

int mul(int arg1, int arg2) {
  return arg1 * arg2;
}

int main() {
  int N, M;
  scanf("%d %d", &N, &M);
  
  int val_sum = sum(N, M);
  int val_sub = sub(N, M);
  int val_mul = mul(N, M);
    
  if (val_sum > val_sub) {
    if (val_sum > val_mul) {
      printf("%d", val_sum);
    }
    else {
      printf("%d", val_mul);
    }
  }
  else {
    if (val_sub > val_mul) {
      printf("%d", val_sub);
    }
    else {
      printf("%d", val_mul);
    }
  }
}


Measured memory_bytes: 128
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {
	LL n, k; cin >> n >> k;
	vector<LL> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i]; a[i]--;
	}

	//周期を計測。
	vector<int> visited(n,-1);
	visited[0] = 0;
	int next = a[0];
	int cnt = 1;
	while (visited[next]==-1) {
		visited[next] = cnt++;
		next = a[next];
	}

	int l = next;

	//ループに入るまでに必要な手数
	int x = visited[l];
	//ループの周期
	int p = cnt - x;

	if (k <= x) {
		next = 0;
		for (int i = 0; i < k; i++) {
			next = a[next];
		}

		cout << next + 1 << endl;
		return 0;
	}

	k = (k - x)%p;

	next = l;
	for (int i = 0; i < k; i++) {
		next = a[next];
	}

	cout << next + 1 << endl;
	return 0;

}

Measured memory_bytes: 5640
using System;

namespace ABC174.Problems
{
    class D
    {
        static void Main()
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var n = int.Parse(Console.ReadLine());
            char[] cs = Console.ReadLine().ToCharArray();

            int res = 0;
            int i = 0;
            int j = n - 1;
            while (true)
            {
                while (i < n  && cs[i] == 'R') i++;
                while (j >= 0 && cs[j] == 'W') j--;
                if (i < j)
                {
                    char temp = cs[i];
                    cs[i] = cs[j];
                    cs[j] = temp;
                    res++;
                } else {
                    break;
                }
            }
            Console.WriteLine(res);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 28576
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *
        
#非再帰バージョン
N = INT()

w = ["a"]

while  w:
    s = w.pop()
    if len(s) == N:
        print(s)
        continue
    else:
        for j in range(len(set(s)), -1, -1):
            t = s+ascii_lowercase[j]
            w.append(t)

Measured memory_bytes: 10640
#include<stdio.h>
#include<string.h>

#define N 200

int main(){
  char ans[N], str[N];
  int n, h, i, j, len;

  while(scanf("%s", ans), ans[0]!='-'){
    scanf("%d", &n);
    for(i=0; i<n; i++){
      scanf("%d", &h);
      len=strlen(ans);
      for(j=0; j<len-h; j++){
	str[j]=ans[h+j];
      }
      for(j=0; j<h; j++){
	str[j+(len-h)]=ans[j];
      }
      for(j=0; j<len; j++){
	ans[j]=str[j];
      }
    }

    printf("%s\n", ans);
    
  }

  return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
typedef long long ll;
typedef pair<ll, ll> P;
template<typename T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template<typename T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}

// ////////////////////////////////////////////

constexpr ll INF = (1ll << 60);
constexpr ll MOD = 1000000007ll;

int main() {
    ll n, m, x;
    cin >> n >> m >> x;
    vector<vector<ll>> a(n, vector<ll>(m));
    vector<ll> c(n);
    REP(i, n){
        cin >> c[i];
        REP(j, m){
            cin >> a[i][j];
        }
    }

    ll ans = INF;
    for(ll bit = 0; bit < (1<<n); bit ++){
        vector<ll> algo(m, 0);
        ll sum = 0;
        REP(i, n){
            if((1<<i) & bit){
                sum += c[i];
                REP(j, m){
                    algo[j] += a[i][j];
                }
            }
        }
        bool flag = true;
        REP(i, m){
            if(algo[i] < x) flag = false;
        }
        if(flag){
            chmin(ans, sum);
        }
    }
    if(ans == INF){
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=lst[a];i;i=nxt[i])
using namespace std;

int read() {
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	int x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

const int N=1e5+5;

int t[N<<1],nxt[N<<1],lst[N],l;
void add(int x,int y) {t[++l]=y;nxt[l]=lst[x];lst[x]=l;}

int n,r,tot,mx,fa[N],rk[N],p[N],k[N],an[N];

void get_far(int x,int y,int d) {
	if (d>mx) mx=d,r=x;
	rep(i,x) if (t[i]!=y) get_far(t[i],x,d+1);
}

void dfs(int x,int y) {
	fa[x]=y;
	rep(i,x) if (t[i]!=y) dfs(t[i],x);
}

int main() {
	n=read();
	fo(i,1,n-1) {
		int x=read(),y=read();
		add(x,y);add(y,x);
	}
	mx=r=0;get_far(1,0,0);int u=r;
	mx=r=0;get_far(u,0,0);int v=r;
	dfs(u,0);
	for(int x=v;x;x=fa[x]) p[++tot]=x,rk[x]=tot;
	fo(i,1,n) {
		if (!rk[i]&&!rk[fa[i]]) {puts("-1");return 0;}
		if (!rk[i]) k[rk[fa[i]]]++; 
	}
	bool rev=0;
	for(int i=1,j=tot;i<=tot;i++,j--) {
		if (k[i]>k[j]) {rev=1;break;}
		if (k[i]<k[j]) {rev=0;break;} 
	}
	if (rev) fo(i,1,tot/2) swap(k[i],k[tot-i+1]);
	int m=0;
	fo(i,1,tot) {
		fo(j,m+1,m+k[i]) an[j]=j+1;an[m+k[i]+1]=m+1;
		m+=k[i]+1;
	}
	fo(i,1,n) printf("%d ",an[i]);
	return 0;
}

Measured memory_bytes: 8960
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)








int main() {
    ll a, b, c, d, e, k;
    cin >> a >> b >> c >> d >> e >> k;
    if(e - a <= k){
        cout << "Yay!" << endl;
    }
    else{
        cout << ":(" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>                                               //scanf,printf
#include <algorithm>                                            //max,min
#include <string>                                               //string
#include <cstring>                                              //strlen,strcat
#include <cctype>                                               //isalpha,tolower
#include <cmath>                                                //sqrt,sin
#include <stack>                                                //top,push
#include <queue>                                                //front,push
#include <vector>                                               //push_back,sort
#include <set>                                                  //insert,begin
#include <map>                                                  //insert,find
#include <list>                                                 //push_front,begin
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>                                               //pow,powf
#define INF (1<<21)
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define ll         long long
#define pl pair<long long, long long>
#define pr pair<int,int>

#define MAX_E 2001
#define MAX_v 1001


struct edge{
  int from,to,cost;
};

edge es[MAX_E];
int d[MAX_v];
int v,e;

bool bellman_ford(int s){
  for(int i=0; i<v; i++){
    d[i]=INF;
  }
  d[s]=0;
  for (int j=0; j<v; j++) {
    for(int i=0; i<e; i++){
      edge e=es[i];
      if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost){
        d[e.to]=d[e.from]+e.cost;
        
        if(j==v-1) return true;
      }
    }
  }
  return false;
}

int main(){
  int r;
  cin>>v>>e>>r;
  for(int i=0; i<e; i++){
    cin>>es[i].from>>es[i].to>>es[i].cost;
  }
  if(bellman_ford(r)) {
    cout<<"NEGATIVE CYCLE"<<endl;
    return 0;
  }
  
  for(int i=0; i<v; i++){
    if(d[i]==INF) cout<<"INF"<<endl;
    else cout<<d[i]<<endl;
  }
}



Measured memory_bytes: 3100
def f_playing_tag_on_tree():
    from collections import deque

    def bfs(tree, distance, first_pos):
        q = deque([(first_pos, -1)])
        while q:
            current, parent = q.pop()
            for child in tree[current]:
                if child == parent:
                    continue
                distance[child] = distance[current] + 1
                q.appendleft((child, current))

    N, U, V = map(int, input().split())
    tree = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    # 両者について、最初にいる場所から他の頂点への移動回数を求める
    dist_aoki = [0] * N
    bfs(tree, dist_aoki, V - 1)
    dist_takahashi = [0] * N
    bfs(tree, dist_takahashi, U - 1)

    ans = 0
    for aoki, takahashi in zip(dist_aoki, dist_takahashi):
        # 注目した頂点 v には高橋くんの方が先に到達できる
        if aoki > takahashi:
            # 青木くんは v の親で高橋くんを捕まえることになるので、
            # v までの距離 - 1 が解となりうる
            ans = max(ans, aoki - 1)
    return ans

print(f_playing_tag_on_tree())

Measured memory_bytes: 29328
c = [list(map(int,input().split())) for _ in range(3)]

check = False
for i in range(101):
  for j in range(101):
    for k in range(101):
      o = c[0][0] - i
      p = c[1][1] - j
      q = c[2][2] - k
      
      if o < 0 or p < 0 or q < 0:
        continue
      
      ls = [[i+o,i+p,i+q],[j+o,j+p,j+q],[k+o,k+p,k+q]]
      if ls == c:
        check = True
        break
        
print("Yes" if check else "No")

Measured memory_bytes: 9116
from functools import lru_cache

N, _ = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

costs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]  # (0), 1...9


@lru_cache(None)
def f(n):
    if n == 0:
        return 0
    values = [f(n-costs[a]) * 10 + a for a in A if n >= costs[a]]
    if len(values) > 0:
        return max(values)
    return -1


[f(i) for i in range(N)]
print(f(N))


Measured memory_bytes: 15680
#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

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, M, K; cin >> N >> M >> K;
    vector<i64> A(N); REP(i, N) cin >> A[i];
    vector<i64> B(M); REP(i, M) cin >> B[i];

    vector<i64> AC(N + 1, 0);
    REP(i, N) AC[i + 1] = AC[i] + A[i];

    vector<i64> BC(M + 1, 0);
    REP(i, M) BC[i + 1] = BC[i] + B[i];

    i64 cnt = 0;
    REP(na, N + 1) {
        i64 t = AC[na];
        i64 rem = K - t;
        i64 nb = (upper_bound(BC.begin(), BC.end(), rem) - BC.begin()) - 1;
        if (nb < 0) continue;
        chmax(cnt, na + nb);
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 9532
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <math.h>
#include <limits>
#include <stdio.h>
#include <queue>

template <typename T>
void vc(T t) {
    std::cout << t << " ";
}

template<typename T, typename... Args>
void vc(T t, Args... args) {
// recursive variadic function
    std::cout << t << " ";
    vc(args...) ;
}

long long dp[402][402];
void once() {
  int n;
  std::cin >> n;
  std::vector<long long> vll(n + 1, 0LL);
  std::vector<long long> sum(n + 1, 0LL);
  for (int i = 1; i <= n; ++i) {
    std::cin >> vll[i];
    sum[i] += sum[i - 1] + vll[i];
  }
  for (int i = 1; i <= 400; ++i)
    for (int j = 1; j <= 400; ++j)
      if (i != j)
        dp[i][j] = std::numeric_limits<long long>::max();

  for (int l = 1; l <= n; ++l)
    for (int i = 1; i + l <= n; ++i)
      for (int k = 0; k < l; ++k)
        dp[i][i + l] = std::min(dp[i][i + l], dp[i][i + k] + dp[i + k + 1][i + l] + sum[i + l] - sum[i - 1]);

  std::cout << dp[1][n] << std::endl;
}

int
main() {
  int n = 1;
  std::ios::sync_with_stdio(false);
  // std::cin >> n;
  while (n--) {
    once();
  }
}

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

int main() {
 string S;
 cin >> S;
 bool a = true;
 for(int i=0;i<3;i++){
  if(S.at(i)==S.at(i+1)){
    a=false;
  }
 }
 if(a){
   cout << "Good" << endl;
 }
   else{
     cout << "Bad" << endl;
   }
}

Measured memory_bytes: 3616
s = gets.chomp

result = true

we = ns = 0
we += 1 if s.include?("E")
we -= 1 if s.include?("W")

ns += 1 if s.include?("S")
ns -= 1 if s.include?("N")

if we == 0 and ns ==0
  puts "Yes"
else
  puts "No"
end


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

map <string,int> p;
int sk[100000];

int main()
{
	string s,t;
	int k,sum,cnt = 0;
	char g;
	cin >> s >> k;
	int len = s.size();
	
	t = s;
	sum = 0;
	for(int i = 0;i < len-1;++i){
		if(t[i] == t[i+1]) t[i+1] = '#',sum++;
	}
	sk[++cnt] = sum;
	p[t] = cnt;
	
	while(1){
		sum = 0;
		g = t[len-1];
		t = s;
		if(g == t[0]) t[0] = '#',sum++;
		for(int i = 0;i < len-1;++i){
			if(t[i] == t[i+1]) t[i+1] = '#',sum++;
		}

		sk[++cnt] = sum;
		if(p.count(t)) break;
		p[t] = cnt;
	}
	int l = cnt - p[t];

	long long ans = 0,ans2 = 0;
	for(int i = 1;i < p[t];++i) ans += sk[i];
	for(int i = p[t];i < cnt;++i) ans2 += sk[i];
	ans += (k-p[t])/l * ans2;
	
	int left = (k-p[t])%l;
	for(int i = p[t];i < p[t]+1;++i) ans += sk[i];
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.Arrays;
class Main{
    public static void main(String[] args) throws IOException {
        int i,tmp;
        int[] A = new int[100];
        String str;
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        for(;(str=in.readLine())!=null;){
            char[] c = str.toCharArray();
            for(i=0;i<c.length;i++){
                tmp = (int)c[i];
                if(64 < tmp && tmp <91) tmp+=32;
                tmp-=97;
                if(tmp < 0 || 27 < tmp) continue;
                A[tmp]+=1;
            }
        }
        for(i=0;i<26;i++){
            System.out.println((char)(97+i)+" : "+A[i]);
        } 
        System.out.flush();
    }
}

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

const int inf = -1000;

int main() {

    int n,d;
    cin>>n>>d;

    int arr[n][d];

    for(int i=0;i<n;++i)
        for(int j=0;j<d;++j)
           cin>>arr[i][j];

      int ct = 0;
     for(int i=0;i<n-1;++i){
        for(int j=i+1;j<n;++j){
                int sum = 0;
        for(int k=0;k<d;++k){
           sum+= (arr[i][k]-arr[j][k])*(arr[i][k]-arr[j][k]);

        }
         if(ceil(sqrt(sum))==floor(sqrt(sum)))
     ct++;
        }



     }
     cout<<ct;
    return 0;
      }


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int N; cin >> N;
    map<string, vector<int>> A = {
            {"gray", {}},
            {"brown", {}},
            {"green", {}},
            {"l_blue", {}},
            {"blue", {}},
            {"yellow", {}},
            {"orange", {}},
            {"red", {}},
            {"other", {}}
    };

    rep (i, 0, N) {
        int a; cin >> a;
        if (1 <= a and a <= 399) A["gray"].push_back(a);
        else if (400 <= a and a <= 799) A["brown"].push_back(a);
        else if (800 <= a and a <= 1199) A["green"].push_back(a);
        else if (1200 <= a and a <= 1599) A["l_blue"].push_back(a);
        else if (1600 <= a and a <= 1999) A["blue"].push_back(a);
        else if (2000 <= a and a <= 2399) A["yellow"].push_back(a);
        else if (2400 <= a and a <= 2799) A["orange"].push_back(a);
        else if (2800 <= a and a <= 3199) A["red"].push_back(a);
        else A["other"].push_back(a);
    }

    int used_space = 0, space = 0;
    for (auto& a : A) {
        if (a.first == "other") continue;
        if (a.second.size() != 0) ++used_space;
        else ++space;
    }

    int min = 0, max = 0;
    if (A["other"].size() != 0) {
        max = used_space + A["other"].size();
        if (used_space == 0) ++used_space;
        min = used_space;
    }
    else {
        if (used_space == 0) {
            ++used_space;
            max = used_space;
            min = used_space;
        }
        else {
            min = used_space;
            max = used_space;
        }
    }

    cout << min << " " << max << endl;
}

Measured memory_bytes: 256
import math

if __name__ == '__main__':
	n,x = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort(reverse=True)

	B = []
	for i in range(0,n-1):
		tmp = A[i] - A[i+1]
		B.append(tmp)

	ans = abs(x-A[0])
	for j in B:
		ans = math.gcd(ans,j)
	print(ans)



Measured memory_bytes: 20276
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>

#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順
//cout << fixed << setprecision(10) << ans << endl;
//int gcd(int a,int b){return b?gcd(b,a%b):a;}

signed main(){
    int l,r,d;
    cin >> l >> r>> d;
    int ans = 0;
    for(int i = l ; i<=r;i++){
        if(i%d == 0){
            ans ++;
        }
    }
    cout << ans << endl;



    return 0;
}

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

int main() {
	int n, m, l, r, lbound = 1, rbound = 100000;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> l >> r;
		lbound = max(lbound, l);
		rbound = min(rbound, r);
		if(lbound > rbound) {
			cout << 0 << endl;
			return 0;
		}
	} cout << rbound - lbound + 1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int i;
  int a,b;
  int tmp;

  a = 0;
  for(i=0;i<4;i++){
    scanf("%d ",&tmp);
    a += tmp;
  }
  b = 0;
  for(i=0;i<4;i++){
    scanf("%d ",&tmp);
    b += tmp;
  }
  if(a<b)printf("%d\n",b);
  else printf("%d\n",a);
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int a[110];
int main()
{
	int n,s=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],s+=a[i];
	s=2*(s%n)>n?s/n+1:s/n;
	long long ans=0;
	for(int i=1;i<=n;i++) ans+=(a[i]-s)*(a[i]-s);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import sys
# list(map(int,input().split()))

#n = int(input())

#print((n+1)//2)

a = [list(map(int,input().split())) for i in range(3)]
n = int(input())
b = [int(input()) for i in range(n)]

for j in range(3):
  if a[j][0] in b and a[j][1] in b and a[j][2] in b:
    print('Yes')
    sys.exit()
  
for j in range(3):
  if a[0][j] in b and a[1][j] in b and a[2][j] in b:
    print('Yes')
    sys.exit()

if a[0][0] in b and a[1][1] in b and a[2][2] in b:
  print('Yes')
  sys.exit()

if a[0][2] in b and a[1][1] in b and a[2][0] in b:
  print('Yes')
  sys.exit()

print('No')


Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define N (long long)(998244353)
#define MAX 500000
using namespace std;

long long factorial[MAX] = {0}, finverse[MAX] = {0},
          inverse[MAX] = {0};

void smodfact() {
  factorial[0] = factorial[1] = 1;
  finverse[0] = finverse[1] = 1;
  inverse[1] = 1;
  for(int i = 2; i < MAX; ++i) {
    factorial[i] = factorial[i - 1] * i % N;
    inverse[i] = N - (inverse[N % i] * (N / i)) % N;
    finverse[i] = finverse[i - 1] * inverse[i] % N;
  }
}

long long calccomb(long long n, long long k) {
  if(n == k && n == 0) return 1;
  if(n < 0 || k < 0 || n < k) return 0;
  return factorial[n] * finverse[k] % N * finverse[n - k] %
         N;
}

// as + bt = GCD(a,b) a,b:const s,t:var(any)
// return GCD(a,b)
long long extGCD(long long a, long long b, long long& s,
                 long long& t) {
  s = 1, t = 0;
  while(b) {
    long long tmp = a / b;
    a -= b * tmp;
    s -= t * tmp;
    swap(a, b);
    swap(s, t);
  }
  return a;
}

// (mod)x+ay=1, calculate y -> a^-1 (mod m) (a,m : coprime)
long long calcinv(long long a, long long m) {
  long long s, t;
  extGCD(a, m, s, t);
  return (s + m) % m;
}

long long mod_pow(long long x, long long n, long long mod) {
  long long res = 1;
  while(n > 0) {
    if(n & 1) (res *= x) %= mod;
    (x *= x) %= mod;
    n >>= 1;
  }
  return res;
}

long long m, n, k;
long long mci[1005] = {0};
long long dp[1005][1005] = {0};

long long solve();

int main() {
  cin >> m >> n >> k;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  if(m < k) return 0;
  smodfact();
  long long ans = mod_pow(m % N, n, N);
  mci[0] = 1LL;
  for(long long i = 0; i < k; ++i)
    mci[i + 1] =
        mci[i] * ((m - i) % N) % N * calcinv(i + 1, N) % N;
  // dp
  dp[0][0] = 1;
  for(long long i = 1; i <= k; ++i)
    for(long long j = 1; j <= i; ++j) {
      if(i != j) {
        dp[i][j] = calccomb(i, j) * dp[j][j] % N;
        (dp[i][j] += dp[i][j - 1]) %= N;
      }
      else {
        dp[i][j] = mod_pow(i % N, n, N);
        dp[i][j] -= dp[i][j - 1];
        (dp[i][j] += N) %= N;
      }
    }

  for(int i = 0; i < k - 1; ++i) {
    ans -= mci[i + 1] * dp[i + 1][i + 1] % N;
    (ans += N) %= N;
  }
  return ans;
}



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

#define _For(idx, from, to, inc, cmp) \
	for(auto idx=(from) ; idx cmp (to) ; inc idx)
#define ForLE(idx, from, to) \
	_For(idx, from, to, ++, <=)
#define ForGE(idx, from, to) \
	_For(idx, from, to, --, >=)
#define ForLT(idx, from, to) \
	_For(idx, from, to, ++, <)
#define ForGT(idx, from, to) \
	_For(idx, from, to, --, >)
#define For(idx, from, to) \
	_For(idx, from, to, ++, <)

std::string Line;
const auto Nextline = [](){
	std::getline(std::cin, Line);
};
#include <iostream>

void DisableIOSync() {
	std::cin.tie(0);
	std::cout.tie(0);
	std::ios::sync_with_stdio(false);
}
constexpr uint64_t Mod = 1000000007;
int main() {
	DisableIOSync();
	Nextline();
	const int N = std::stoi(Line);
	std::string s[2];
	Nextline();
	std::swap(s[0], Line);
	Nextline();
	std::swap(s[1], Line);

	int cur = 0;
	enum class Type {
		// a
		// a
		A,
		// bb
		// cc
		B,
		End
	};
	const auto NextDomino = [&cur, &s](){
		if(int(s[0].length()) == cur)
			return Type::End;
		if(s[0][cur] == s[1][cur]) {
			cur += 1;
			return Type::A;
		} else {
			// Type B
			cur += 2;
			return Type::B;
		}
	};
	uint64_t npat;
	Type prev = NextDomino();
	if(prev == Type::A) {
		npat = 3;
	} else {
		// (3P2)
		npat = 6;
	}
	
	for(;;) {
		const Type next = NextDomino();
		switch(next) {
			case Type::A:
				if(prev == Type::A) {
					// A -> A
					npat *= 2;
					npat %= Mod;
				} else {
					// B -> A
				}
				break;
			case Type::B:
				if(prev == Type::A) {
					// A -> B
					npat *= 2;
					npat %= Mod;
				} else {
					// B -> B
					npat *= 3;
					npat %= Mod;
				}
				break;
			case Type::End:
				goto END;
		}
		prev = next;
	}
	END:
	std::cout << npat << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define M 100010
#define N 410
int n,m,a[M],b[M],f[N][N],c[N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>a[i]>>b[i];
	for(int i=1;i<=n;i++){
		f[i][i]=1;
		for(int j=m;j;j--){
			int x=f[i][a[j]],y=f[i][b[j]];
			if(x&&y){
				c[i]=1;
				break;
			}
			else if(x)f[i][b[j]]=1;
			else if(y)f[i][a[j]]=1;
		}
	}
	int r=0;
	for(int i=1;i<n;i++){
		if(c[i])continue;
		for(int j=i+1;j<=n;j++){
			if(c[j])continue;
			int ok=1;
			for(int k=1;k<=n;k++)
				if(f[i][k]&&f[j][k])ok=0;
			r+=ok;
		}
	}
	cout<<r;
}

Measured memory_bytes: 1664
#include<stdio.h>

int main(){

int i,j,k,h,n,m;

scanf("%d %d",&n,&m);
int A[n][m];
int b[m];



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

for(k = 0; k < m;k++){
  scanf("%d",&b[k]);
  }


for(i = 0; i < n;i++){
int c = 0;
  for(h = 0; h < m;h++){
  c += A[i][h]*b[h];
  }
printf("%d\n",c);
}

return 0;
}


Measured memory_bytes: 2064
<?php
fscanf(STDIN, '%d %d %d %d', $a, $b, $c, $d);

if ((abs($a - $b) <= $d && abs($b - $c) <= $d) || abs($a - $c) <= $d) {
    echo 'Yes' . PHP_EOL;
} else {
    echo 'No' . PHP_EOL;
}

Measured memory_bytes: 4856