akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(i=a;i<=b;i++)
#define rep2(i,a,b,c) for(i=a;i<=b;i+=c)
#define maxn 100000
queue<int> lin;
int jar[maxn+1];
vector<int> jaj[maxn+1];

void bfs(){
	lin.push(1);
	int dep,i,ke;
	while(!lin.empty()){
		dep=lin.front();lin.pop();
		rep(i,0,(int)jaj[dep].size()-1){
			ke=jaj[dep][i];
			if(jar[ke]==-1){
				jar[ke]=jar[dep]+1;
				lin.push(ke);
			}
		}
	}
}

int main(){
	int N,i,A;
	cin>>N;
	rep(i,1,N){
		cin>>A;
		jaj[i].pb(A);
	}
	memset(jar,-1,sizeof(jar));
	jar[1]=0;
	bfs();
	cout<<jar[2]<<"\n";
}


Measured memory_bytes: 6272
#include<iostream>
#include<cmath>
#include<unordered_map>
#include<math.h>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#include<iomanip>
#include<string>
#include<map>
#define PI 3.14159265
#define mod 998244353    
using namespace std;

 

void func(){
   string s , t;
   cin >> s >> t;
   
   int n = s.size() , m = t.size();
   vector<vector<long long>> dp(n + 1, vector<long long> (m + 1 , 0));

   for(int i = 0 ; i <= n ; ++i){
     for(int j = 0; j <= m ; ++j){
       if(i == 0){
         dp[i][j] = 0;
       }
       else if(j == 0){
         dp[i][j] = 0; 
       }
       else if(s[i - 1] == t[j - 1]){
         dp[i][j] = dp[i - 1][j - 1] + 1;
       }
       else{
         dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]);
       }
     }
   }

string ans;
int ptr1 = n , ptr2 = m;
//cout << ptr1 << " " << ptr2 << "\n";

while (ptr1 > 0 && ptr2 > 0)
{
    if(s[ptr1 - 1] == t[ptr2 - 1]){
      ans = s[ptr1 - 1] + ans;
      --ptr2;
      --ptr1;
    }
    else{
      if(dp[ptr1 - 1][ptr2] >= dp[ptr1][ptr2 - 1]){
        --ptr1;
      }
      else{
        --ptr2;
      }
    }

   
}

 cout << ans << "\n";

}

int main(){
    int t = 1 , cnt = 0 ;
  // cin >> t;
    
    while(t--){
        
        func();
    }
}

Measured memory_bytes: 70784
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
	string s,t;
	cin>>s>>t;
	int n = s.length(), m = t.length();
	int i = 0, mc = 1001;
	while(i<=(n-m)) {
		int c = 0;
		string r = s.substr(i,m);
		for(int j=0;j<m;j++) {
			if(r[j]!=t[j]) {
				c++;
			}
		}
		mc = min(mc,c);
		i++;
	}
	cout<<mc;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int test = 1;
	while(test--) {
		solve();
	}
}


Measured memory_bytes: 3648
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
  int N, x[361] = {};
  cin >> N;
  for (int i = 1; i <= N; i++) {
    int M, D, V, S;
    cin >> M >> D >> V >> S;
    int a = (M - 1) * 30 + D + V - 1;
    int b = (M - 1) * 30 + D;
    for (int k = 0; k < V; k++) x[(b + k) % 360] = max(S, x[(b + k) % 360]);
    for (int j = 1; j <= 360; j++) {
      x[(a + j) % 360] = max(S - j, x[(a + j) % 360]);
      x[(b - j + 360) % 360] = max(S - j, x[(b - j + 360) % 360]);
    }
  }
  sort(x, x + 361);
  cout << x[1] << endl;
}



Measured memory_bytes: 3136
Q, H, S, D = map(int,input().split())
N = int(input())
ans = 0
H = min(2*Q, H)
S = min(2*H, S)
if 2 * S < D:
    ans = S * N
else:
    if N % 2 == 0:
        ans = D * N // 2
    else:
        ans = D * (N-1) // 2 + S
print(ans)

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

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

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

void vprint(vector<ll> A){
    ll L = A.size();
    FOR(i, 0, L){
        if(i) cout << ' ';
        cout << A[i];
    }
    cout << endl;
}

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

    // input
    ll W, H, x, y;
    cin >> W >> H >> x >> y;

    double area = W*H / 2.0;
    cout << setprecision(20);
    cout << area << " ";

    if(W%2==0 && H%2==0 && W/2==x && H/2==y){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
void solve(std::string S){
    bool s1 = S[0] == 'R';
    bool s2 = S[1] == 'R';
    bool s3 = S[2] == 'R';
    if( s1 && s2 && s3){
      cout << 3 << endl;
    } else if(!( s1 || s2 || s3)){
      cout << 0 << endl;
    } else if(s2 && (s1 || s3)){
      cout << 2 << endl;
    } else {
      cout << 1 << endl;
    }
}
 
int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 3632
#include "bits/stdc++.h"
#pragma optimize("unroll-loops");
#pragma optimize("Ofast");
// #include "pch.h"    
using namespace std;

#ifdef DEBUG_BUILD
#  define DEBUG(x) cerr << x
#else
#  define DEBUG(x) do {} while (1)
#endif

#define imie(x) do { std::cerr << #x << ": " << x << std::endl; } while (0)

using ll = long long;
const ll nax = 1e7 + 10;
const int mod = 1e9 + 7;
vector<int> primes;

int main() {
    
    int a,b,c,d,e;
    cin >> a >> b >> c >> d >> e;
    if(a == 0) {
        cout << 1 << "\n";
    }else if(b == 0) {
        cout << 2 << "\n";
    }else if(c == 0) {
        cout << 3 << "\n";
    }else if(d == 0) {
        cout << 4 << "\n";
    }else{
        cout << 5 << "\n";
    }
    return 0;
    
}































Measured memory_bytes: 3564
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=0
for i in range(n):
  if(a[i]>b[i]):
    c+=b[i]
  elif(b[i]>=a[i]+a[i+1]):
    c+=a[i]+a[i+1]
    a[i+1]=0
  else:
    c+=b[i]
    a[i+1]=a[i+1]+a[i]-b[i]
print('{0}'.format(c))

Measured memory_bytes: 18380
s = gets.chomp.to_s
n = s.length
srev = s.reverse
b = s.slice(0..((n-1)/2-1))
c = s.slice(((n+3)/2)-1..n-1)
brev = b.reverse
crev = c.reverse
if s == srev and b == brev and c == crev
  puts "Yes"
else
  puts "No"
end


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

int main(){
	int i = 1;
	while(true){
		int x;
		cin >> x;
		
		if(x == 0) break;
		
		cout << "Case " << i++ << ": " << x << "\n";
	}
	cout << flush;
	
	return 0;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll p=1e9+7;
int a[N];
ll inv(ll a,ll p) { //p为素数,a<p
    if(a==1)return 1;
    return (p-p/a)*inv(p%a,p)%p;
}
ll C(ll n,ll m){
    ll res=1;
    for(ll i=1,j=n-m+1;i<=m;++i,++j){
        res=res*inv(i,p)%p*j%p;
    }
    return res;
}
int main(){
    ll n,m;
    cin>>n>>m;
    ll res=0;
    ll C1=1,C2=1;
    for(int i=0;i<=min(m,n-1);++i){
        res=(res+C1*C2%p)%p;
        C1=C1*inv(i+1,p)%p*(n-i)%p;
        C2=C2*inv(i+1,p)%p*(n-i-1)%p;
    }
    cout<<res;
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline


h, n = map(int, input().split())

AB = [(0, 0)]
for _ in range(n):
    a, b = map(int, input().split())
    AB.append((a, b))

DP = []
for _ in range(n + 1):
    DP.append([0] + [float("inf")] * h)

for i in range(1, n + 1):
    a, b = AB[i]
    for j in range(1, h + 1):
        if j - a < 0:
            DP[i][j] = min(DP[i - 1][j], b)
        else:
            DP[i][j] = min(DP[i - 1][j], DP[i][j - a] + b)

print(DP[n][h])


Measured memory_bytes: 382600
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int n, m;
int used[60];
int a[60][60];
int a1[60], a2[60];

void func(int x) {
    used[x] = 1;
    imfor(i, n) {
        if (used[i] == 0 && a[x][i] == 1) {
            used[i] = 1;
            func(i);
        }
    }
}

int main() {
    
    cin >> n >> m;
    
    imfor(i, m) {
        cin >> a1[i] >> a2[i];
        a1[i]--;
        a2[i]--;
        a[a1[i]][a2[i]] = 1;
        a[a2[i]][a1[i]] = 1;
    }
    int ans = 0;
    imfor(i, m) {
        a[a1[i]][a2[i]] = 0;
        a[a2[i]][a1[i]] = 0;
        fill(used, used + n, 0);
        func(a1[i]);
        imfor(j, n) {
            if (used[j] == 0) {
                ans++;
                break;
            }
        }
        a[a1[i]][a2[i]] = 1;
        a[a2[i]][a1[i]] = 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  
  if(S == "Sunny"){
    cout << "Cloudy" << endl;
  }else if(S == "Cloudy"){
    cout << "Rainy" << endl;
  }else if(S == "Rainy"){
    cout << "Sunny" <<endl;
  }
}

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

using namespace std;
using namespace __gnu_pbds;

#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

struct int_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash {
    size_t operator()(pii x) const {
        return int_hash{}(x.first) ^ (int_hash{}(x.second) << 16);
    }
};

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<cd> vcd;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<vector<pii>> vvpii;
typedef vector<vector<pll>> vvpll;
typedef unordered_map<int, int, int_hash> umpii;
typedef unordered_map<ll, ll, int_hash> umpll;
typedef unordered_set<int, int_hash> usi;
typedef unordered_set<ll, int_hash> usll;
typedef unordered_set<pii, pair_hash> uspii;
typedef queue<int> qi;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = numeric_limits<int>::max();
const int MX = 100001; //check the limits, dummy

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

    double n; cin >> n;
    int lo = 0, hi = n;
    while(hi - lo > 1) {
        int mid = (hi - lo) / 2 + lo;
        if(mid * 1.08 >= n) hi = mid;
        else lo = mid;
    }

    if(hi * 1.08 >= n + 1) cout << ":(" << endl;
    else cout << hi << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll N, A[100000];

int main(void) {
  cin >> N;
  REP(i, 0, N) cin >> A[i];

  sort(A, A + N, greater<ll>());

  ll sum = 0;
  REP(i, 0, N) sum += A[i];

  ll ans = N;
  REP(i, 0, N) {
    sum -= A[i];
    if(sum * 2 < A[i]) {
      ans = i + 1;
      break;
    }
  }
  cout << ans << endl;
}


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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

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

int ans = C - (A - B);
if(ans < 0) ans = 0;
print(ans);
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define drop(x) cout << (x) << '\n', exit(0)
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
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; }
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    string S;
    cin >> S;
    ll A = S[0] - '0', B = S[1] - '0', C = S[2] - '0', D = S[3] - '0';


    rep(i, 1 << 3){
        ll total = A;
        string ans = to_s(A);
        if(i & (1 << 0)) total += B, ans += "+";
        else total -= B, ans += "-";
        ans += to_s(B);

        if(i & (1 << 1)) total += C, ans += "+";
        else total -= C, ans += "-";
        ans += to_s(C);

        if(i & (1 << 2)) total += D, ans += "+";
        else total -= D, ans += "-";
        ans += to_s(D);
        ans += "=7";

        if(total == 7) drop(ans);
    }
    

    return 0;
}

Measured memory_bytes: 256
import sys
def main():
    input = sys.stdin.readline
    A,B,Q=map(int, input().split())
    S=[int(input()) for _ in range(A)]
    T=[int(input()) for _ in range(B)]
    X=[int(input()) for _ in range(Q)]
    from bisect import bisect_left
    INF=10**11
    for x in X:
        sr = bisect_left(S, x)
        tr = bisect_left(T, x)
        sl,tl=sr-1,tr-1
        ans=INF
        if sl >= 0 and tl >= 0:
            ans = min(ans, abs(S[sl]-T[tl]) + min(abs(S[sl]-x), abs(T[tl]-x)))
        if sl >= 0 and tr < B:
            ans = min(ans, abs(S[sl]-T[tr]) + min(abs(S[sl]-x), abs(T[tr]-x)))
        if sr < A and tl >= 0:
            ans = min(ans, abs(S[sr]-T[tl]) + min(abs(S[sr]-x), abs(T[tl]-x)))
        if sr < A and tr < B:
            ans = min(ans, abs(S[sr]-T[tr]) + min(abs(S[sr]-x), abs(T[tr]-x)))
        print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 148444
#include <stdio.h>
int main(void){
   int S, h, m, s;
   
   scanf("%d",&S);
   if(S <= 86400){
       s = S % 60;
       h = ((S - s) / 60) / 60;
       m = ((S - s) / 60) % 60;
   }
   else{
       return 0;
   }
   printf("%d:%d:%d\n",h, m, s);
   return 0;
}


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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int main(){
  int n;cin >> n;
  vector<int> v(n), c(n);

  for(int i=0; i<n; ++i)cin >> v[i];
  for(int i=0; i<n; ++i)cin >> c[i];
  
  int x = 0, y = 0;
  for(int i=0; i<n; ++i){
    if(v[i]>c[i]){
      x += v[i];
      y += c[i];
    }
  }
  cout << abs(x-y) << endl;
    
}

Measured memory_bytes: 3632
s = input()
t = input()
n = len(s) - len(t) + 1
m = len(t)
ans = 0
for i in range(n):
    c = 0
    for j in range(m):
        if s[j+i] == t[j]:c+=1
    
    ans = max(c,ans)
print(m-ans)

Measured memory_bytes: 9068
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int ll
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
#define IN(a) cin >> a
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    rep(i,3){
        string s; IN(s);
        cout << s[i];
    }
    
    return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()

#define cMOD 1000000007ULL
#define cINF ((1ull<<62)-1)
#define cINFINT ((1<<30)-1)

int main()
{
    ll h,w; cin>>h>>w;
    vector<vector<ll>> rock( h, vector<ll>( w, 0 ) );
    REP( i, h )
    {
        string s;cin>>s;
        ll start = 0; ll ru = 0;
        REP(j,w)
        {
            if( s[j] == '.' ) ++ru;
            if( s[j] == '#' )
            {
                for( ll k = start; k < j; ++k) rock[i][k] = ru;
                start = j+1;
                ru = 0;
            }
        }
        for( ll k = start; k < w; ++k) rock[i][k] = ru;
    }

    ll maxx = 0;
    REP(j,w)
    {
        ll start = 0; ll maxxx = 0;
        REP(i,h)
        {
            if( rock[i][j] == 0 )
            {
                for( ll k = start; k < i; ++k)
                {
                    maxx = max( maxx, rock[k][j] + maxxx - 1 );
                }
                start = i+1;
                maxxx = 0;
            }
            else ++maxxx;
        }
        for( ll k = start; k < h; ++k)
        {
            maxx = max( maxx, rock[k][j] + maxxx - 1 );
        }
    }

    cout << maxx << endl;

    return 0;
}

Measured memory_bytes: 31616
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
int A[MAX_N];
bitset<2000 * 2000 + 10> dp[2]; 

void bitshow(int at) {
	vector<int> vec;
	rep(i, 0, 10) {
		vec.pb(dp[at][i]);
	}
	debug(vec);
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	dp[0][0] = 1;
	int s = 0;
	int now = 0, nex = 1;
	rep(i, 0, N) {
		dp[nex] = dp[now] << A[i];
		dp[nex] |= dp[now];
		swap(now, nex);
		s += A[i];
	}
	s = (s + 1) / 2;
	for(int i = s; ; i++) {
		if(dp[now][i]) {
			cout << i << "\n";
			return;
		}
	}
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
#ifdef LOCAL
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

int main() {
  int64_t n, m;
  std::cin >> n >> m;

  m /= 2;
  std::cout << min(m, n + (m - n) / 2) << std::endl;
  return 0;
}


Measured memory_bytes: 3520
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
const int inf = 1 << 30;
const ll linf = 1e18;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

string S;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> S;
    cout << (S[0] != S[1] || S[1] != S[2] ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MIN INT_MIN
#define MAX INT_MAX
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define endk "\n"
#define rep(i,j,k,inc) for(int i=j;i<k;i+=inc)
#define modd 1000000007
using namespace std;
void solve();
void dfs(int i);
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    time_t start,end;
    time(&start);
    solve();
    time(&end);
    double t= double(end - start); 
/*  cout << fixed<< t<< setprecision(5)<<endl;*/
    return 0; 
}
vector<int> adj[111111];
int n,m,ans=0,vis[111111],dp[111111];

void solve(){
	cin>>n>>m;
	rep(i,0,m,1){
		int u,v;
		cin>>u>>v;
		adj[u].PB(v);
	}
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++){
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endk;
}

void dfs(int node){
	vis[node]=1;
	for(int i=0;i<adj[node].size();i++){
		if(!vis[adj[node][i]]){
			dfs(adj[node][i]);
		}
		dp[node]=max(dp[node],dp[adj[node][i]]+1);
	}
}


Measured memory_bytes: 8960
#include <iostream>

using namespace std;

int calsum ( int x )
{
  int sum = 0;

  while ( x > 0 ) {
    sum += x%10;
    x /= 10;
  }

  return sum;
}


int main()
{
  int N,a,b;
  int sum = 0;

  cin >> N >> a >> b;

  for ( int i = 1; i <= N; ++i ) {
    int tmp = calsum(i);
    if ( tmp >= a && tmp <= b ) sum += i;
  }

  cout << sum << "\n";
}


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

int main() {
    vector< vector<int> > c(3, vector<int>(3));
    for (int i = 0; i < 3; i++){
        for (int j = 0; j < 3; j++){
            cin >> c[i][j];
        }
    }
    int tmp;
    for (int i = 0; i < 2; i++){
        tmp = c[i+1][0] - c[i][0];
        for (int j = 1; j < 3; j++){
            if (c[i+1][j] - c[i][j] != tmp){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    for (int j = 0; j < 2; j++){
        tmp = c[0][j+1] - c[0][j];
        for (int i = 1; i < 3; i++){
            if (c[i][j+1] - c[i][j] != tmp){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

		int ans = 0;
		if (a>=k) {
			ans = k;
		} else if (a+b>=k) {
			ans = a;
		} else {
			ans = a - (k-a-b);
		}
		sc.close();
		System.out.println(ans);
	}
}


Measured memory_bytes: 27032
import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }

void main() {
  auto NK = readln.split.to!(ulong[]);
  auto K = NK[1];
  auto P = readln.split.to!(ulong[]);

  void solve() {
    auto Pd = P.map!(x => cast(double)(x+1) / 2.0f);
    double max = Pd[0..K].sum;
    double current = max;

    foreach(i; K..NK[0]) {
      current += Pd[i] - Pd[i-K];
      if (max < current) {
        max = current;
      }
    }

    writefln("%.10f", max);
  }

  solve();
}


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

typedef long long ll;

using namespace std;

ll cost(ll h) {
    if (h == 1) {
        return 1;
    }
    return 1 + cost(h / 2) * 2;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h;
    cin >> h;
    cout << cost(h) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define ARRAY_LENGTH(array) sizeof(array)/sizeof(*array)
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; }
const int INF = 1000100100;

int main() {
    ll N, T, A;
    cin >> N >> T >> A;

    ll ans = 1;
    long double min_dif = INF;
    REP(i, N) {
        ll H;
        long double tmp, tmp_dif;
        cin >> H;
        tmp = T - H*0.006;
        tmp_dif = abs(A - tmp);

        if(i == 0 || tmp_dif < min_dif) {
            min_dif = tmp_dif;
            ans = i + 1;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3680
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <bitset>
using namespace std;

int main(void){
  int N;
  cin >> N;
  vector<int> A;
  vector<int> B;
  vector<int> C;
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    A.push_back(a);
  }
  for(int i=0;i<N;i++){
    int b;
    cin >> b;
    B.push_back(b);
  }
  for(int i=0;i<N;i++){
    int c;
    cin >> c;
    C.push_back(c);
  }
  
  sort(A.begin(),A.end());
  //sort(B.begin(),B.end());
  sort(C.begin(),C.end());
  
  int64_t total = 0;
  for(int i=0;i<N;i++){
    int b = B[i];
    auto itA = lower_bound(A.begin(),A.end(),b);
    auto itC = upper_bound(C.begin(),C.end(),b);
    total += (itA-A.begin()) * (C.end()-itC);
  }
 
  cout << total << endl;
}


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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n, k;
  cin >> n >> k;
  
  vector<ll> a(n);
  for(int i = 0; i < n; i++) cin >> a.at(i);
  
  vector<ll> b(n + 1), c(n + 1);
  for(int i = 0; i < n; i++){
    b.at(i + 1) = b.at(i) + a.at(i);
    c.at(i + 1) = c.at(i) + max<ll>(0, a.at(i));
  }
  
  ll ans = 0;
  for(int i = 0; i + k <= n; i++){
    ll keep = 0;
    if(b.at(i + k) - b.at(i) > 0) keep += b.at(i + k) - b.at(i);
    keep += c.at(i) + c.at(n) - c.at(i + k);
    
    ans = max(ans, keep);
  }
  
  cout << ans << '\n';
}

Measured memory_bytes: 2560
n,m=gets.split.map(&:to_i)
a=gets.split.map(&:to_i).sort
bc=m.times.map{gets.split.map(&:to_i)}.sort_by{|b,c|-c}
idx=0
a.sort!
bc.sort_by!{|b, c| -c }
idx = 0
bc.each{|b, c|
  while idx <  n && a[idx] < c && b > 0
    a[idx] = c
    idx += 1
    b -= 1
  end
}
puts a.inject:+

Measured memory_bytes: 21024
import io
import sys


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


def make_divisors(n):
  divisors = []
  for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n // i)

  # divisors.sort()
  return divisors


test_str = '''
4
1 0 1 0
'''
#
# 1 1 1

def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()
  li = IN_L_I()

  tmp = [False] * n
  tmp2 = [False] * n
  for i, b in enumerate(reversed(li)):
    ci = n - i - 1
    # print("hoge:",i,b,ci)
    if b == 1 and not tmp[ci]:
      tmp[ci] = True
      tmp2[ci] = True

    if b == 0 and tmp[ci]:
      tmp[ci] = False
      tmp2[ci] = True

    if tmp2[ci]:
      # print(ci, " || ",make_divisors(ci + 1))
      for j in make_divisors(ci + 1):
        if j != ci + 1:
          tmp[j - 1] = not tmp[j - 1]

    # print(tmp)
    # print(tmp2)

  puts = [i for i, x in enumerate(tmp2) if x]
  print(len(puts))
  if len(puts) > 0:
    print(" ".join([str(i + 1) for i in puts]))
  return None


def B():
  return None


def C():
  return None


MAIN()


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

int main() {
  int A,B,C;
  cin >> A >> B >> C;
  
  vector<int>D(3); D = {A, B, C};
  
  sort(D.begin(),D.end());
  
  if (D.at(0) == 5 && D.at(1) == 5 && D.at(2) == 7) {
   cout << "YES" << endl;
  }
  
  else {
    cout << "NO" << endl;
  }
}

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

using namespace std; 
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>; 

#define INF LONG_MAX;
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

int main(){
  int N,K;
  cin>>N>>K;
  vector<pair<ll,ll>>X(N);
  for(int i=0;i<N;i++)cin>>X[i].first>>X[i].second;
  vector<ll>x(N),y(N);
  ll ans=INF;
  for(int i=0;i<N;i++)x[i]=X[i].first,y[i]=X[i].second;
  for(auto x1:x){
    for(auto y1:y){
      for(auto x2:x){
        for(auto y2:y){
          ll sum=0;
          for(int i=0;i<N;i++){
            if(x1<=X[i].first&&X[i].first<=x2&&
                y1<=X[i].second&&X[i].second<=y2){
              sum++;
            }
          }
          if(sum>=K){
            ll s=abs(x1-x2)*abs(y1-y2);
            ans=min(s,ans);
          }
        }
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
<?php
list($n) = ints();
$a = ints();
$cntOdd = 0;
for ($i = 0; $i < $n; ++$i)
    if ($a[$i] % 2) ++$cntOdd;
echo 3 ** $n - 2 ** ($n - $cntOdd);
echo PHP_EOL;
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 16068
from sys import stdin,stdout
from math import gcd,sqrt
from collections import deque
input=stdin.readline
R=lambda:map(int,input().split())
I=lambda:int(input())
S=lambda:input().rstrip('\n')
L=lambda:list(R())
P=lambda x:stdout.write(x)
hg=lambda x,y:((y+x-1)//x)*x
pw=lambda x:1 if x==1 else 1+pw(x//2)
chk=lambda x:chk(x//2) if not x%2 else True if x==1 else False
print(list(map(int,input().split())).index(0)+1)

Measured memory_bytes: 65308
import sys

n = int(input())
d = [int(x) for x in input().split()]

if d[0] != 0:
    print(0)
    sys.exit()

d.sort()

if d[1] == 0:
    print(0)
    sys.exit()
    
dd = []
c = 1
for i in range(1, n):
    if d[i-1]==d[i]:
        c += 1
    else:
        dd.append(c)
        c = 1
dd.append(c)

if len(dd) != d[-1]+1:
    print(0)
    sys.exit()

ans = 1
for i in range(1, len(dd)):
    ans *= dd[i-1] ** dd[i]

ans = ans % 998244353
print(ans)


Measured memory_bytes: 56364
import math


n, k = map(int, input().split())

prob = 0

for dice in range(1, n+1):
	if dice >= k:
		prob += 1/n 
	else:
		prob += (1/n) * (1 / math.pow(2, (math.ceil(math.log2(k / dice)))))
		
print(prob)

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

int main()
{
	int N;
	cin >> N;
	vector<long long> A( N );
	for( int i = 0; i < N; i++ ) {
		cin >> A[i];
	}

	long long ans = 0;
	for( int i = 0; i < N; i++ ) {
		if( i == 0 ) {
			if( A[i] != 0 ) {
				ans = -1;
				break;
			}
		}
		else {
			if( A[i] > A[i - 1] + 1 ) {
				ans = -1;
				break;
			}
		}
	}
	if( ans == 0 ) {
		for( int i = 0; i < N; i++ ) {
			if( i == 0 ) continue;
			else {
				if( A[i] == A[i - 1] + 1 ) ans++;
				else ans += A[i];
			}
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 4852
#include<iostream>
using namespace std;
const int N=101;
int n,x,c[N],M;
int main()
{
	cin>>n;
	while(n--&&cin>>x)
		c[x]++,M=max(M,x);
	if(M%2==0)
		c[M/2]++;
	for(int i=1;i<N;i++)
		if((i<M/2&&c[i])||(i==(M+1)/2&&c[i]!=2)||(M/2<i&&i<=M&&c[i]<2))
		{
			cout<<"Impossible";
			return 0;
		}
	cout<<"Possible";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<list>

#define endl "\n"
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;

int main(){
    int n;
    ll k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];

    ll ans = 0;
    for(int i=0;i<n-1;i++){
        for(int j=i;j<n;j++){
            if(a[i] > a[j]) ans = (ans+1) %MOD;
        }
    }
    ans = ans * k %MOD;

    ll ten = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i] > a[j]) ten = (ten+1) %MOD;
        }
    }
    ans = ( ans + ten * ( k*(k-1)/2 %MOD ) ) %MOD;

    cout<< ans % MOD <<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 1000000007
ll fact[50];
#define eps 1e-9
#define INF 1e18
ll power(ll a,ll b,ll c){
  ll ans=1;
  while(b){
    if(b&1){
      ans=ans*a%c;
    }
    a=a*a%c;
    b=b/2;
  }
  return ans;
}
ll ncr(ll n,ll r){
    if(r>n)return 0;
    if(r==n)return 1;
    ll z=fact[n];
    z=z*power(fact[r],mod-2,mod)%mod;
    z=z*power(fact[n-r],mod-2,mod)%mod;
    return z;
}
ll min(ll a,ll b){return a<b?a:b;}
ll max(ll a,ll b){return a>b?a:b;}
ll gcd(ll a,ll b){
    if(b==0)return a;
    return gcd(b,a%b);
}

int main() {
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   int n; cin>>n;
   string s; cin>>s;
   ll dp[n+1][3];
   memset(dp,0,sizeof(dp));
   map<char,int> m;
   m['R']=0;
   m['G']=1;
   m['B']=2;
   dp[1][m[s[0]]]=1;
   for(int i=1;i<n;++i){
    for(int j=0;j<3;j++)dp[i+1][j]=dp[i][j];
    dp[i+1][m[s[i]]]++;
   }
   ll ans=0;
   for(int i=0;i<n;++i){
    for(int j=i+1;j<n;j++){
        if(s[i]==s[j])continue;
        if(m[s[j]]!=0&&m[s[i]]!=0){ans=ans+dp[n][0]-dp[j+1][0];
            int x=j-i;
            if(j+x<n&&m[s[j+x]]==0)ans--;
        }
        if(m[s[j]]!=1&&m[s[i]]!=1){ans=ans+dp[n][1]-dp[j+1][1];
            int x=j-i;
            if(j+x<n&&m[s[j+x]]==1)ans--;
        }
        if(m[s[j]]!=2&&m[s[i]]!=2){ans=ans+dp[n][2]-dp[j+1][2];
            int x=j-i;
            if(j+x<n&&m[s[j+x]]==2)ans--;
        }
        }

   }
   cout<<ans;
}


Measured memory_bytes: 3684
#include "bits/stdc++.h"
#define N 200000
using namespace std;
char s[N + 5];
int main(int argc, char const *argv[]) {
	scanf("%s", s);
	int ans = strlen(s);
	for (int i = 1, flag = 0; i < strlen(s); i++) {
		if (s[i] == s[i - 1] && !flag)
			flag = 1, ans--, i++;
		else
			flag = 0;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
inline int read(){
	char c=getchar();int t=0,f=1;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
	return t*f;
}
int n;
struct node{
	int v,p;
}e[maxn<<1];
int h[maxn],cnt=1;
inline void add(int a,int b){
	e[++cnt].p=h[a];
	e[cnt].v=b;
	h[a]=cnt;
	e[++cnt].p=h[b];
	e[cnt].v=a;
	h[b]=cnt;
}
int du[maxn],cur,fr[maxn],val[maxn];
void dfs(int u,int fa,int col){
	int ck=0;
	for(int i=h[u];i;i=e[i].p){
		int v=e[i].v;
		if(v==fa)continue;
		ck++;
		if(col==ck)ck++;fr[i/2]=ck;
		dfs(v,u,ck);
	}
	cur=max(cur,ck);
}
int main(){
	n=read();
	for(int i=1;i<n;i++){
		int a=read(),b=read();
		add(a,b);
		du[a]++;du[b]++;
	}
	dfs(1,0,0);
	printf("%d\n",cur);
	for(int i=1;i<n;i++)printf("%d\n",fr[i]);
	return 0;
}


Measured memory_bytes: 4736
#include <stdio.h>
#include <stdlib.h>

enum{
    ROOT,
    InternalNode,
    LEAF
};
typedef struct _node{
    int parent;
    int depth;
    int type;   //0:root,1:internal node,2:leaf
    int *child;
    int cCnt;
}NODE;

int getroot(NODE node[],int n){
    int i;
    for(i=0;i<n;i++)if(node[i].parent==-1)return i;
    
    return -1;
}
void getDepth(NODE node[],int id){
    if(node[id].depth==-1)node[id].depth=node[node[id].parent].depth+1;
    if(node[id].parent==-1)node[id].type=ROOT;
    else if(node[id].cCnt==0)node[id].type=LEAF;
    else node[id].type=InternalNode;
    
    int i;
    for(i=0;i<node[id].cCnt;i++)getDepth(node,node[id].child[i]);
    return;
}

void printNode(NODE node[],int n){
    int i,j;
    for(i=0;i<n;i++){
        printf("node %d: parent = %d, depth = %d, ",i,node[i].parent,node[i].depth);
        switch(node[i].type){
            case ROOT:
                printf("root");
                break;
            case InternalNode:
                printf("internal node");
                break;
            case LEAF:
                printf("leaf");
                break;
        }
        printf(", [");
        for(j=0;j<node[i].cCnt;j++){
            if(j==0)printf("%d",node[i].child[j]);
            else printf(", %d",node[i].child[j]);
        }
        printf("]\n");
    }
    return;
}
int main(void){
    int i,j;
    
    int n;
    scanf("%d\n",&n);
    
    NODE node[n];
    for(i=0;i<n;i++){
        node[i].parent=-1;
        node[i].depth=-1;
        node[i].type=-1;
        node[i].child=NULL;
        node[i].cCnt=0;
    }
    
    int id,k,c;
    for(i=0;i<n;i++){
        scanf("%d %d ",&id,&k);
        if(k>0)node[id].child=(int*)malloc(sizeof(int)*k);
        node[id].cCnt=k;
        for(j=0;j<k;j++){
            scanf("%d",&c);
            node[id].child[j]=c;
            node[c].parent=id;
        }
    }
    
    int root;
    root=getroot(node,n);
    if(root==-1)return -1;
    
    node[root].depth=0;
    node[root].type=ROOT;
    getDepth(node,root);
    
    printNode(node,n);
    
    for(i=0;i<n;i++){
        if(node[i].child!=NULL)free(node[i].child);
    }
    
    return 0;
}



Measured memory_bytes: 5280
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define tc int t; cin>>t; while(t--)
#define mod 1000000007
 
using namespace std;
 
void fastio(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
}
 
int main(){
    fastio();
    int n,k;
    cin>>n>>k;
    int a[n+1];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    
    cout<<ceil(double(n-1)/double(k-1));
    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int main(){
	
	int N;

	cin >> N;

	int ans = 0;

	for(int i = 0; i < N; i++){
		int num1, num2;
		cin >> num1 >> num2;
		ans += num2 - num1 + 1;
	}

	cout << ans << endl;

	return 0;
}



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

int main(){
	
	int a,b,c,d,n;
	
	while(cin >> n){
		int ans=0;
		
		for(a=0;a<=9;a++){
			for(b=0;b<=9;b++){
				for(c=0;c<=9;c++){
					for(d=0;d<=9;d++){
						if(a+b+c+d==n) ans++;
					}
				}
			}
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define GET_BIT(n, i) (((n) & (1LL << ((i)-1))) >> ((i)-1)) // i start from 1
#define SET_BIT(n, i) ((n) | (1LL << ((i)-1)))
#define CLR_BIT(n, i) ((n) & ~(1LL << ((i)-1)))
typedef pair<int, int>  pii;
typedef pair<ll, ll>  pl;
typedef vector<int>   vi;
typedef vector<ll>    vl;
typedef vector<pii>   vpii;
typedef vector<pl>    vpl;
typedef vector<vi>    vvi;
typedef vector<vl>    vvl;
void myInit();
int mpow(int base, int exp);
void ipgraph(int m);
void dfs(int u, int par);
const int MOD = 1000000007;
const int N = 3e5, M = N;
//=========TQR==============
vi g[N];

int main() {
	myInit();
	FIO;
	int n, x, t, q;
	cin >> n >> x >> t;
	q = n / x;
	if (n % x)
		q++;
	cout << t*q << endl;
	return 0;
}

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

int mpow(int base, int exp) {
	base %= MOD;
	int result = 1;
	while (exp > 0) {
		if (exp & 1) result = ((ll)result * base) % MOD;
		base = ((ll)base * base) % MOD;
		exp >>= 1;
	}
	return result;
}

void ipgraph(int n, int m) {
	int i, u, v;
	while (m--) {
		cin >> u >> v;
		g[u - 1].pb(v - 1);
		g[v - 1].pb(u - 1);
	}
}

void dfs(int u, int par) {
	for (int v : g[u]) {
		if (v == par) continue;
		dfs(v, u);
	}
}

Measured memory_bytes: 10684
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

# dic={}
# for i in range(n):
#     x,y=xy[i]
#     dic[(x,y)]=1
if n==1:
    print(1)
    quit()
cnt=0
sadic=defaultdict(int)
for i in range(n):
    x,y=xy[i]
    for j in range(n):
        if i==j:
            continue
        x2,y2=xy[j]
        p,q=x-x2,y-y2
        sadic[(p,q)]+=1
# print(sadic)
print(n-max(sadic.values()))

Measured memory_bytes: 74600
# Wrote in Mar 4, 2020 19:10 by reetok
require 'time'
require 'prime'
require 'bigdecimal'
def inp(type=:to_i,spst=" ")
  return eval("gets.chomp.split(#{spst}).map(&:#{type})")
end
def inpf() return self.inp(:to_f," ") end
def inps() return self.inp(:to_s," ") end
def r_up(a, b) (a/b).ceil end
def r_down(a, b) (a/b).floor end
def sum(a) a.inject(:+) end
def big(a,b) return (a>b)? a:b end
def small(a,b) return (a<b)? a:b end
def minp(n,datatype=:to_i)
  t = []
  n.times do
    t.push(eval("gets.chomp.#{datatype.to_s}"))
  end
end
def yes() puts "Yes" end
def no() puts "No" end
def ynju(bool,yes="Yes",no="No") puts (bool ? yes : no) end
class Integer
  def divisor_list
    devisors = [1]
    2.upto(self/2) do |i|
      devisors << i if self%i == 0
    end
    devisors << self
    return devisors.uniq.sort
  end
end
class Array
  def upper(a) #aより上
    self.sort.select{|n|n>=a}
  end
  def downer(a) #aより下
    self.sort.select{|n|n<=a}
  end
end

#---------------

n = gets.to_i
a = inp
puts [a.min,a.max,sum(a)].join(" ")


Measured memory_bytes: 7524
#include<stdio.h>
int main(void)
{
	int w[10],k[10];
	int i,j,temp;
	int wm,km;
	for(i=0;i<10;i++){
		scanf("%d",&w[i]);
	}
	for(i=0;i<9;i++){
		for(j=i+1;j<10;j++){
			if(w[i]<w[j]){
				temp=w[i];
				w[i]=w[j];
				w[j]=temp;
			}
		}
	}
	wm=w[0]+w[1]+w[2];
	
	for(i=0;i<10;i++){
		scanf("%d",&k[i]);
	}
	for(i=0;i<9;i++){
		for(j=i+1;j<10;j++){
			if(k[i]<k[j]){
				temp=k[i];
				k[i]=k[j];
				k[j]=temp;
			}
		}
	}
	km=k[0]+k[1]+k[2];
	
	printf("%d %d\n",wm,km);
	return 0;
}

Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,c;
  cin >> a >> b;
  a *= 2;
  c = a*2;
  if (b >= a && b <= c && b % 2 == 0) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}

Measured memory_bytes: 3620
import collections
import itertools

N=int(input())
S=[input() for i in range(N)]

counted = collections.Counter(S)

# 最頻値を求める
m = max(counted.values())

# 頻出数の文字を集める
chars = [key for key, value in counted.items()
             if value == m]
chars=sorted(chars)
for a in chars:
  print(a)

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

#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++)
template<class T> void out(T a){cout<<a<<'\n';}

int main(){
  int n,q;
  cin>>n>>q;
  dsu d(n);
  rep(i,q){
    int k,u,v;
    cin>>k>>u>>v;
    if(k==0) d.merge(u,v);
    else out(d.same(u,v));
  }
}


Measured memory_bytes: 3936
#include <bits/stdc++.h>
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 FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

struct ST {
  ll w, s, v;
};
bool operator<(const ST& a, const ST& b){
  return a.w+a.s < b.w+b.s;
}

ll dp[1005][10005];

int main(){
  int N;
  cin >> N;
  vector<ST> v;
  rep(i,N){
    ll w, s, a;
    cin >> w >> s >> a;
    v.push_back((ST){w,s,a});
  }
  sort(ALLOF(v));

  rep(i,1005) rep(j,10005) dp[i][j] = -1;
  dp[0][0] = 0;

  ll ret = 0;
  rep(i,N){
    rep(j,10005){
      if(dp[i][j] < 0) continue;
      dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
      ret = max(ret, dp[i][j]);      
      if(j<=v[i].s){
        ret = max(ret, dp[i][j] + v[i].v);
        if(i < N-1 && j+v[i].w < 10005){
          dp[i+1][j+v[i].w] = max(dp[i+1][j+v[i].w], dp[i][j] + v[i].v);
        }
      }
    }
  }
  
  cout << ret << endl;
  
  return 0;
}


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

int main() {
    int N;
    cin >> N;
    
    if (N % 1000 == 0){
        cout << "Yes" << endl;
    }
    else if (N % 1111 < 9){
        cout << "Yes" << endl;
    }
    else if (N % 1111 > 1105){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

}

Measured memory_bytes: 256
import Control.Applicative ((<$>), (<*>))
import Control.Monad (replicateM)

import Data.List (sort, unfoldr)
import Data.Char (isSpace)

import Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B

getIntList :: IO [Integer]
getIntList = unfoldr f <$> B.getContents
    where
        f s = do
            (n, s') <- B.readInteger s
            return (n, B.dropWhile isSpace s')

main :: IO ()
main = solve <$> getIntList >>= print

myCeiling :: Integer -> Integer -> Integer
myCeiling m n = ceiling $ fromInteger m / fromInteger n

solve :: [Integer] -> Integer
solve (n:xs) = (+4) $ myCeiling n $ head $ sort xs

Measured memory_bytes: 380
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String a = sc.next();
    String alast = String.valueOf(a.charAt(a.length() - 1));
    String b = sc.next();
    String bfirst = String.valueOf(b.charAt(0));
    String blast = String.valueOf(b.charAt(b.length() - 1));
    String c = sc.next();
    String cfirst = String.valueOf(c.charAt(0));
    String ans = "NO";
    if(alast.equals(bfirst) && blast.equals(cfirst)) ans = "YES";
    System.out.println(ans);
  }
}

Measured memory_bytes: 24788