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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define pll         pair<long,long>
#define vi          vector<int>
#define vll         vector<ll>
#define vii         vector<pii>
#define vpll        vector<pair<ll,ll>>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define mod        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define rem(i,a,b)  for(int i=a;i>b;i--)
#define mp(a,b)     make_pair(a,b)
#define vvi(a,b,name)    vector<vector<int>> name(a,vector<int>(b,-1))


void solve(){
    ll n,k;
    cin>>n>>k;
    vpll v;
    ll a,b;
    rep(i,0,n){
        cin>>a>>b;
        v.pb({a,b});
    }
    sort(all(v));
    ll pos=v[0].y;
    int j=0;
    while(pos<k){
        j++;
        pos+=v[j].y;
    }
    //j=j==0?0:j-1;
    cout<<v[j].x;

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 2420
import * as fs from "fs";

const input = (fs.readFileSync("/dev/stdin", "utf8") as string).split("\n");

//const [n, m] = input[0].split(" ").map((x: string): number => +x);
//const a = input[1].split(" ").map((x: string): number => +x);

const [n, m] = input[0].split(' ').map((x: string): number => +x);

if (n===m){
	console.log('Yes');
}else{
	console.log('No');
}

Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define prt(v) cout<<(v)<<"\n";
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
#define endl "\n"
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;

// Combination Table
ll C[51][51]; // C[n][k] -> nCk
void comb_table(int N){
for(int i=0;i<=N;++i){
for(int j=0;j<=i;++j){
if(j==0 or j==i){
C[i][j]=1LL;
}else{
C[i][j]=(C[i-1][j-1]+C[i-1][j]);
}
}}}


signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll A;
    cin >> A;
    ll B;
    cin >> B;
    vector<ll> v(N,0);
    for(ll i=0;i<N;++i)cin>>v[i];
    sort(v.rbegin(), v.rend());
    ll sum=0;
    for(ll i=0;i<A;++i)sum+=v[i];
    cout << fixed << setprecision(6);
    prt((ld)((ld)sum/(ld)A))
    ll mark=v[A-1];
    ll count1=0,count2=0;
    for(ll i=0;i<A;++i)if(v[i]==mark)count1++;
    for(ll i=A;i<N;++i)if(v[i]==mark)count2++;
    count2+=count1;

    comb_table(50);

    if(v[0]!=v[A-1]){
        prt(C[count2][count1])
    }
    else {
        ll ans=0;
        for(ll i=count1;i<=min(count1+B-A,count2);++i)ans+=C[count2][i];
        prt(ans)
    }

    return 0;
}


Measured memory_bytes: 256
/*

#include<iostream>
#include<vector>
using namespace std;
int main(void){

int n,m;
cin >> n >> m;

vector<vector<int>>A;
for (int x = 0; x < n; x++){
for (int y = 0; y < m; y++){
cin >> A[x][y];
}
}
vector<int> b;
for (int y = 0; y < m; y++){

cin >> b[y];

}

vector<int>c;
for (int x = 0; x < n; x++){
for (int y = 0; y < m; y++){
c[x] += A[x][y] * b[y];

}
}

for (int i = 0; i < n; i++){
cout << c[i]<<endl;
}
//system("pause");

return 0;
}
*/

#include <iostream>


#include <vector>

using namespace std;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int> > matrix(n, vector<int>(m));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> matrix[i][j];
		}
	}
	vector<int> vec(m);
	for (int i = 0; i < m; ++i)
	{
		cin >> vec[i];
	}
	for (int i = 0; i < n; ++i)
	{
		int sum = 0;
		for (int j = 0; j < m; ++j)
		{
			sum += matrix[i][j] * vec[j];
		}
		cout << sum << endl;
	}
}

int main(void)
{
	solve();
	return(0);
}

Measured memory_bytes: 1256
#!/usr/bin/perl

my ($n) = map {$_ - 0} split(/\s+/o,<STDIN>);
my @a = map {$_ - 0} split(/\s+/o,<STDIN>);

my $tc = 0;
for(my $i=0;$i<$n;$i++){
  $tc += &f($a[$i]);
}
print "$tc\n";

exit(0);

sub f {
  my $v = shift;
  my $ct = 0;
  while($v>0){
    last if ( $v & 1 ) == 1;
    $ct++;
    $v >>= 1;
  }
  return $ct;
}



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

#define ll long long
#define pb push_back
#define st first
#define sc second
#define mp make_pair

using namespace std;

const int e = 1e6 + 69;

int main()
{
    ll x;
    int n;
    cin >> x >> n;
    map<ll, ll>kt;
    for(int i=1; i<=n; i++){
        int cur;
        cin >> cur;
        kt[cur] ++;
    }
    ll ans = 1e18;
    ll kq;
    for(int i=-200; i<=200; i++){
        if(kt[i] == 0){
            if(abs(i - x) < ans){
                ans = abs(i - x);
                kq = i;
            }
        }
    }
    cout << kq;
}



Measured memory_bytes: 3660
#include<bits/stdc++.h>
char ch[100010];
int ans;
int main() {
	scanf("%s", ch);
	int n = strlen(ch);
	for (int i = 1; i < n; i++)
		if (ch[i] != ch[i - 1])
			ans++;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 384
/*input
4 10
6 1 2 7
*/

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;

#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define mod 1000000007
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define out(container) cout << #container << " = "; for (auto it : container) cout << it << " "; cout << endl;


template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
    int x = 1 % mod;
    while(b){
        if(b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

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

  ll w, h, x, y;
  cin >> w >> h >> x >> y;
  bool many = false;
  if (w == 2 * x && h == 2 * y) {
    many = true;
  }
  ld ans = (w * 1.0 * h) / 2.0;
  cout << fixed << setprecision(15) << ans << " ";
  cout << many << endl;

  return 0;
}

Measured memory_bytes: 256
def resolve():
  n = int(input())
  p = list(map(int, input().split()))

  ans = 0
  for i in range(1, n-1):
    if (p[i-1] < p[i] and p[i] < p[i+1]) or (p[i-1] > p[i] and p[i] > p[i+1]):
      ans += 1

  print(ans)
  return

if __name__ == "__main__":
  resolve()



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

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll K; cin >> K;
  string S; cin >> S;
  if ((ll)S.size() <= K) {
    cout << S << endl;
  }else {
    S.resize(K);
    cout << S << "..." << endl;
  }

  return 0;
}



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

//オーバーフロー
//コーナーケース

typedef long long ll;
int n;
ll dp[1<<18][5];
ll a[1<<18];

ll mi(ll &a, ll b) {
    a = min(a, b);
    return a;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j < 5; j++) 
            dp[i][j] = 1e18;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 5; j++) {
            for (int k = j; k < 5; k++) {
                switch (k) {
                    case 0:
                        mi(dp[i][k], dp[i - 1][j] + a[i]);
                        break;
                    case 1:
                        if (a[i] == 0) {
                            mi(dp[i][k], dp[i - 1][j] + 2);
                            break;
                        }
                        mi(dp[i][k], dp[i - 1][j] + (a[i] & 1));
                        break;
                    case 2:
                        mi(dp[i][k], dp[i - 1][j] + ((a[i] + 1) & 1));
                        break;
                    case 3:
                        if (a[i] == 0) {
                            mi(dp[i][k], dp[i - 1][j] + 2);
                            break;
                        }
                        mi(dp[i][k], dp[i - 1][j] + (a[i] & 1));
                        break;
                    case 4:
                        mi(dp[i][k], dp[i - 1][j] + a[i]);
                        break;
                }
            }
        }
    }

    cout << mi(dp[n][4], mi(dp[n][3], mi(dp[n][2], mi(dp[n][1], dp[n][0])))) << endl;
    return 0;
}


Measured memory_bytes: 9984
# -*- coding: utf-8 -*-

# input
N, T = map(int, input().split())
c = [0] * N
t = [0] * N
for i in range(N):
    _c, _t = map(int, input().split())
    c[i] = _c
    t[i] = _t

# solve
ans = 1001
for i in range(N):
    if t[i] <= T:
        ans = min(ans, c[i])

# output
print(ans if ans != 1001 else 'TLE')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iomanip>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

pair<ll, ll> dp[400][400];

int main() {
  int n;
  cin >> n;
  rep(i, n) {cin >> dp[i][i].first; dp[i][i].second = 0;}
  for (int i=1; i<n; i++) for (int j=0; j<n-i; j++) {
    dp[j+i][j].first = dp[j+i-1][j].first + dp[j+i][j+i].first;
    dp[j+i][j].second = dp[j+i-1][j].second + dp[j+i][j+i].second;
    rep(k, i-1) {
      dp[j+i][j].second = min(dp[j+i][j].second, 
                              dp[j+i-2-k][j].second+dp[j+i][j+i-1-k].second);
    } dp[j+i][j].second += dp[j+i][j].first;
  }
  cout << dp[n-1][0].second << endl;
}


Measured memory_bytes: 2560
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <utility>
#include <set>
#include <map>
#include <tuple> 
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
using namespace  std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(long long (i)=0, i_bound = (long long)(n); (i)<i_bound; ++i)
#define FOR(i, a, b) for(long long (i)=(a); (i)<(b); ++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
const long long MOD = static_cast<long long>(1e9) + 7LL;
const long long INF = 1234567891234567890LL;
signed main(){
    int a, b, c; cin>>a>>b>>c;
    if(a-b>=c) cout << 0 <<endl;
    else cout << c - a +b <<endl;
    return 0;
}

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

//#define int long long
using bll = boost::multiprecision::cpp_int;
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=(1<<31)-1=2147483647
constexpr ll INF = (ll)1e18;//(1LL<<63)-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr int dx[2]={1,0};
constexpr int dy[2]={0,1};
#ifdef LOCAL_ENV
	#define debug(var) std::cout<<#var" = "<<var<<std::endl
#else
	#define debug(var)
#endif
#define p(var) std::cout<<var<<std::endl
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define all(a) (a).begin(), (a).end()
#define PI (acos(-1))
template<typename T> inline T power(T x, T n){ return n ? power(x*x%MOD,n/2)*(n%2?x:1)%MOD : 1; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	for (int i = 0, len = v.size(); i < len; ++i){
		s << v[i]; if (i < len - 1) s << "\t";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	for (int i = 0, len = vv.size(); i < len; ++i){
		s << vv[i] << endl;
	}
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
	s << "{" << endl;
	for (typeof(m.begin()) itr = m.begin(); itr != m.end(); ++itr){
		s << "\t" << (*itr).first << " : " << (*itr).second << endl;
	}
	s << "}" << endl;
	return s;
}

/*-----8<-----8<-----*/

constexpr ll W_MAX = 8;


ll H, W;
char A[10][10];

void input() {
	scanf("%lld%lld", &H, &W);
	rep(i, H) scanf("%s", A[i]);
}

bool solve() {

	ll x=0,y=0;
	A[0][0]='.';
	while(1){
		if(x>0 && A[x-1][y]=='#'){
			return false;
		}
		if(y>0 && A[x][y-1]=='#'){
			return false;
		}

		if(x!=H-1 && y!=W-1 && A[x][y+1]=='#' && A[x+1][y]=='#'){
			return false;
		}

		if(x==H-1 && y==W-1){
			return true;
		}

		rep(i,2){
			ll nx=x+dx[i];
			ll ny=y+dy[i];

			if(nx==H)continue;
			if(ny==W)continue;
			if(A[nx][ny]=='#'){
				A[nx][ny]='.';
				x=nx;
				y=ny;
				goto a;
			}
		}
		a:;
	}

	
	
}

signed main() {
	input();
	if (solve()){
		printf("Possible\n");
	}else{
		printf("Impossible\n");
	}
	return 0;
}


Measured memory_bytes: 256
N, X, Y = [int(_) for _ in input().split()]
# X = int(input())
cnt = [0 for i in range(1, N+1)]
for i in range(1, N+1):
    for j in range(i+1, N+1):
        d = min(j-i, abs(X-i) + 1 + abs(j-Y))
        cnt[d] += 1
for i in range(1, N):
    print(cnt[i])

Measured memory_bytes: 3444
#include <chrono>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pldll;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<ld> vld;
#define newl '\n'
const ll M = 1e9 + 7;
const ll N = 1e2;
const ll INF = LONG_MAX;
#define REP(i, a, b) for (int i = a; i < b; i++)
#define LOG_TWO_N 10
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);

ll gcd(ll a,ll b)
{
    if(a==0)
    {
        return b;
    }
    else
    {
        return gcd(b%a,a);   
    }
}
ll lcm(ll a,ll b)
{
    return a*b/gcd(a,b);
}
int f(char c)
{
    return (int)c-96;
}

template <class T>
void print(vector<T> &vec, int inc = 0, bool lb = true)
{
    for (auto v : vec)
        cout << v + inc << " ";
    if (lb)
        cout << newl;
}

void solve(ll t)
{
    int n; cin >> n;
    //vector<int> a(n);
    ll msf=0;
    ll ans = 0;
    REP(i, 0, n) {
        //cin >> a[i];
        ll x; cin >> x;
        if(i==0) msf = x;
        else {
            if(x < msf) {
                ans += msf-x;
            } else {
                msf = x;
            }
        }
    }
    cout << ans << newl;
}

int main()
{
    fast;

    ll t = 1;
    //cin >> t;
    while (t--)
    {
        solve(t);
    }

    return 0;
}

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

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
    return '"' + s + '"';
}

string to_string(const char* s) {
    return to_string((string) s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cout << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << " " << to_string(H);
    debug_out(T...);
}

#ifndef ONLINE_JUDGE
#define debug(...) cout<<"LINE ("<< __LINE__ << ") : [" << #__VA_ARGS__ << "] -> ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , t ;
    cin >> n >> t ;
    int ans = INT_MAX; 
    while(n--){
        int a , b ; 
        cin >> a >> b ; 
        if(b<=t){
            ans = min(ans , a);
        }
    }
    if(ans == INT_MAX)
        cout << "TLE"; 
    else
        cout << ans;
        
    return 0 ;
}




Measured memory_bytes: 3664
import numpy as np
n, W = map(int, input().split())
dp = np.zeros((n + 1, W + 1))

for i in range(n):
    w, v = map(int, input().split())
    dp[i + 1] = dp[i]
    if w <= W:
        dp[i + 1][w:] = np.maximum(dp[i][:W - w + 1] + v, dp[i][w:])
print(int(dp[n][W]))

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

int main(){
  int N, M, a, O = 1, f = 0;
  string U[300], T;
  int i, j, k;
  cin>>N;
  for(i = 0; i < N; i++)cin>>U[i];
  
  cin>>M;
  
  for(i = 0; i < M; i++){
    	cin>>T;
	j = 0;
		while(j < N){
			f = 0;
			if((int)T.size() == (int)U[j].size()){
      				for(k = 0; k <(int)T.size(); k++){
					if(U[j][k] != T[k]){
						  break;
					}
				}
					if(k == (int)T.size()){
						if(O){
	 		 				cout<<"Opened by "<<T<<endl;
	  				 		 O = 0;
							f = 1;
							break;
						} else{
	 					  	cout<<"Closed by "<<T<<endl;
	  		 				 O = 1;
							f = 1;
							break;
						}
					}
				
    			 }
			if(f == 1) break;
			j++;
		}
		if(j == N) cout<<"Unknown "<<T<<endl;
	
	}
	
  return 0;
}




Measured memory_bytes: 3196
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
string s[2010];
int h,w;
int l[2010][2010];
int r[2010][2010];
int u[2010][2010];
int d[2010][2010];
int main(){
    int ans = 0;
    cin>>h>>w;
    rep(i,h) cin>>s[i];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#') l[i][j]=0;
            else if(j==0) l[i][j]=1;
            else l[i][j]=l[i][j-1]+1;
        }
    }
    for(int j=0;j<w;j++){
        for(int i=0;i<h;i++){
            if(s[i][j]=='#') u[i][j]=0;
            else if(i==0) u[i][j]=1;
            else u[i][j]=u[i-1][j]+1;
        }
    }
    //right
    for(int i=h-1;i>=0;i--){
        for(int j=w-1;j>=0;j--){
            if(s[i][j]=='#') r[i][j]=0;
            else if(j==w-1) r[i][j]=1;
            else r[i][j]=r[i][j+1]+1;
        }
    }
    for(int j=w-1;j>=0;j--){
        for(int i=h-1;i>=0;i--){
            if(s[i][j]=='#') d[i][j]=0;
            else if(i==h-1) d[i][j]=1;
            else d[i][j]=d[i+1][j]+1;
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            ans = max(l[i][j]+r[i][j]+d[i][j]+u[i][j]-3,ans);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 67456
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cctype>
#include <queue>
#define ll long long 
#define ri register int 
using namespace std;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=100005;
int tag[maxn];
int n,m;
int main(){
	int l,r;
	read(n),read(m);
	for(ri i=1;i<=m;i++){
		read(l),read(r);
		tag[l]++,tag[r+1]--;
	}
	int ans=0;
	for(ri i=1;i<=n;i++){
		tag[i]=tag[i]+tag[i-1];
		if(tag[i]==m)ans++;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>

using namespace std;

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

	vector <long long> l(87);
	l[0] = 2;
	l[1] = 1;

	for (int i = 2; i <= n; i++) {
		l[i] = l[i - 2] + l[i - 1];
	}
	cout << l[n] << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>

#include<queue>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF 1844674407370955161
typedef long long int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007


class DisjointSet{
    public:
        vector<int> rank, p;

        DisjointSet(){
        }

        DisjointSet(int size){
            rank.resize(size, 0);
            p.resize(size, 0);
            for (int i = 0; i < size;i++)
                makeSet(i);
        }
        void makeSet(int x){
            p[x] = x;
            rank[x] = 0;
        }

        bool same(int x,int y){
            return findSet(x) == findSet(y);
        }
        void unite(int x,int y){
            link(findSet(x), findSet(y));
        }
        void link(int x,int y){
            if(rank[x]>rank[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank[x]==rank[y]){
                    rank[y]++;
                }
            }
        }
        int findSet(int x){
            if(x!=p[x]){
                p[x] = findSet(p[x]);
            }
            return p[x];
        }
};

class Edge{
    public:
        int source, target;
        ll cost;
        Edge(int source = 0, int target = 0, ll cost = 0):
        source(source),target(target),cost(cost){}
        bool operator < (const Edge &e) const{
            return cost < e.cost;
        }
};

ll kruskal(int N,vector<Edge> edges){
    ll totalCost = 0;
    sort(edges.begin(), edges.end());
    DisjointSet dset = DisjointSet(N + 1);

    for (int i = 0; i < N;i++)
        dset.makeSet(i);

    int source, target;
    REP(i,0,edges.size()){
        Edge e = edges[i];
        if(!dset.same(e.source,e.target)){
            totalCost += e.cost;
            dset.unite(e.source, e.target);
        }
    }

    return totalCost;
}

int main()
{
    int N;
    cin >> N;
    vector<pair<ll, int> > x;
    vector<pair<ll, int> > y;
    
    REP(i,0,N){
        ll xx, yy;
        cin >> xx >> yy;
        x.push_back(make_pair(xx, i));
        y.push_back(make_pair(yy, i));
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    vector<Edge> edges;
    REP(i, 0, N - 1)
    {
        edges.push_back(Edge(x[i].second, x[i + 1].second, abs(x[i].first - x[i + 1].first)));
        edges.push_back(Edge(y[i].second, y[i + 1].second, abs(y[i].first - y[i + 1].first)));
    }
    cout << kruskal(N, edges) << endl;
}

Measured memory_bytes: 11360
import Control.Monad

main :: IO ()
main = do
  s1 <- getLine
  if s1 == "0 0"
    then return ()
    else do
      ls <- replicateM 4 getLine
      let ls' = map (sum . map (read :: String -> Int) . words) (s1:ls)
          ls'' = zip ls' ["A","B","C","D","E"]
          ans = solve ls''
      putStrLn ans
      main

solve :: [(Int,String)] -> String
solve ls = toString (foldl1 comp ls)
  where
    toString :: (Int,String) -> String
    toString (a,b) = b ++ " " ++ show a
    comp :: (Int,String) -> (Int,String) -> (Int,String)
    comp (a,b) (c,d)
      | a < c = (c,d)
      | otherwise = (a,b)

Measured memory_bytes: 4048
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<N;i++)
#define INF 1e9
typedef long long LL;
const LL MOD = 1e9+7;

int main() {
  LL A, B, C;
  cin >> A >> B >> C;
  cout <<  max(LL(0), C - (A - B)) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map> 
using namespace std;
int main(){
    set<long> st;
    map<long,int> mp;
    int n;
    cin >> n;
    long a;
    for(int i = 0;i<n;i++){
        cin >> a;
        mp[a]++;
        st.insert(a);
    }
    int ans = 0;
    for(auto itr = st.begin();itr != st.end();itr++){
        if(mp[*itr]>=*itr) ans+=mp[*itr]-*itr;
        else ans+=mp[*itr];
    }
    cout << ans << endl;
}

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

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

	queue<long long> q;
	for (int i = 1; i < 10; ++i) {
		q.push(i);
	}

	for (int i = 0; i < k - 1; ++i) {
		long long x = q.front();
		q.pop();

		int r = x % 10;
		if (r > 0) {
			q.push(x * 10 + r - 1);
		}

		q.push(x * 10 + r);

		if (r < 9) {
			q.push(x * 10 + r + 1);
		}
	}

	cout << q.front();
	
	return 0;
}
	

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

using namespace std;

int mini, how, N, M, val[100009], ap[100009], block[100009];
vector < int > v[100009];

void dfs (int nod)
{
    ap[nod] = 1;
    if (val[nod] < mini)
        mini = val[nod], how = nod;
    for (auto it : v[nod])
        if (ap[it] == 0)
            dfs (it);
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=N; i++)
    scanf ("%d", &val[i]);
while (M --)
{
    int x, y;
    scanf ("%d %d", &x, &y), x ++, y ++;
    v[x].push_back (y);
    v[y].push_back (x);
}
long long ans = 0;
int cnt = 0;
for (int i=1; i<=N; i++)
    if (ap[i] == 0)
        mini = 1e9 + 5, dfs (i), block[how] = 1, ans += mini, cnt ++;
if (cnt == 1)
{
    printf ("0\n");
    return 0;
}
vector < int > h;
for (int i=1; i<=N; i++)
    if (block[i] == 0)
        h.push_back (val[i]);
sort (h.begin (), h.end ());
if (h.size () < cnt - 2)
{
    printf ("Impossible\n");
    return 0;
}
for (int i=0; i<cnt - 2; i++)
    ans += h[i];
printf ("%lld\n", ans);
return 0;
}


Measured memory_bytes: 7420
import fractions

def main():
    A, B, C, D = map(int, input().split())

    def num_of_multiples(st, ed, m):
        a = st % m
        a0 = st + (m - a)
        if a == 0:
            a0 = st
        if a0 > ed:
            return 0
        b = ed % m
        b0 = ed - b
        num = (b0 - a0)
        if num % m != 0:
            raise Exception()
        return (b0 - a0) // m + 1
    
    nc = num_of_multiples(A, B, C)
    nd = num_of_multiples(A, B, D)
    ncd = num_of_multiples(A, B, C * D // fractions.gcd(C, D))
    print(B - A + 1 - (nc + nd - ncd))


main()

Measured memory_bytes: 5048
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

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

const double PI = acos(-1);
typedef long long ll;
#define int ll
#define fori(n) for(int i=0; i<int(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cind(d) double d; cin>>d;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a, n) vd a(n); fori(n) { cin>>a[i]; }

typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;

void solve() {
    cini(k);
    int ans=0;
    for(int i=1; i<=k; i++) {
        for(int j=1; j<=k; j++) {
            int g=__gcd(i,j);
            for(int l=1; l<=k; l++) {
                ans+=__gcd(g,l);
            }
        }
    }
    cout<<ans<<endl;
}

signed main() {
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    solve();
}



Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <regex>
#include <stack>
#include <queue>
#include <vector>
#define MAX_N 100
#define INF 10000000

using namespace std;


int n;
string s;
int a[200000];

void solve() {
	string a = "No";
	for (int i = 0; i < s.length()-1; i++) {
		if (s[i] == 'A'&&s[i + 1] == 'C') a = "Yes";
	}
	cout << a << endl;
}

int main() {
	cin >> s;
	solve();
	return 0;
}

Measured memory_bytes: 256
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int H, W, K;
int dp[110][10];

signed main() {
    cin >> H >> W >> K;

    dp[0][0] = 1;
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            if(dp[i][j] == 0) continue;
            for(int bit=0; bit<(1<<(W-1)); bit++) {
                bool ok = true;
                for(int i=0; i<W-2; i++) {
                    if((bit >> i & 1) and (bit >> (i+1) & 1)) ok = false;
                }

                if(ok) {
                    // cerr << "bit = " << bitset<10>(bit).to_string() << endl;

                    if(j > 0 and (bit >> (j-1) & 1)) {
                        // ひだり
                        (dp[i+1][j-1] += dp[i][j]) %= MOD;
                    }
                    else if(bit >> j & 1) {
                        // みぎ
                        (dp[i+1][j+1] += dp[i][j]) %= MOD;
                    }
                    else {
                        (dp[i+1][j  ] += dp[i][j]) %= MOD;
                    }
                }
            }
        }
    }

    cout << dp[H][K-1] << endl;
    return 0;
}

Measured memory_bytes: 256
# import itertools
# import math
# import sys
import numpy as np

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# S = input()

# d = sorted(d.items(), key=lambda x:x[0]) # keyでsort
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement([i for i in range(1, M + 1)], N))
# print(a[0][0])
# print(conditions[0])

A = np.array(A)
B = np.array(B)

cum_A = np.cumsum(A)
cum_A = np.insert(cum_A, 0, 0)
cum_B = np.cumsum(B)
cum_B = np.insert(cum_B, 0, 0)

j = M
max_num = 0
for i in range(N + 1):
    while(True):
        # j -= 1
        if j < 0:
            break
        minute = cum_A[i] + cum_B[j]
        if minute <= K:
            if i + j > max_num:
                max_num = i + j
            break
        j -= 1

print(max_num)

Measured memory_bytes: 58548
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main(int argc, const char * argv[]) {
  
    int n;
    
    scanf("%d",&n);
    int nx=0,ny=0,nt = 0;
    for(int i=0;i<n;i++){
        int t,x,y;
        
        scanf("%d %d %d",&t,&x,&y);
        
        int dist = abs(x-nx);
        dist += abs(y-ny);
        
        if(dist > (t-nt)){
            printf("No\n");
            return 0;
        }
        int diff = t-nt; //3
        
        int mindist = abs(x-nx) + abs(y-ny)-1; //1
        
        if( !((diff-mindist) &1)){
            printf("No\n");
            return 0;
        }
        
        nx = x;
        ny = y;
        nt = t;
    }
    
    
    printf("Yes\n");
    return 0;
}


Measured memory_bytes: 256
//16-2
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define segment_size 65536
#define ROOP() while (true)

int main(){
    int H,R;
    cin >> H >> R;
    if(H+R == 0) cout << 0 << endl;
    if(H+R < 0) cout << -1 << endl;
    if(H+R > 0) cout << 1 << endl;
    return 0;
}



Measured memory_bytes: 3100
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=998244353;
struct Nums{
    long long n;
    vector<long long> kaijo;
    Nums(int N){
        n=N;
        kaijo.push_back(1);
        for(long long i=1;i<=n;i++){
            kaijo.push_back((kaijo[i-1]*i)%MOD);
        }
    }
    long myPow(long x, long n, long m){
        if(n == 0)
            return 1;
        if(n % 2 == 0)
            return myPow(x * x % m, n / 2, m);
        else
            return x * myPow(x, n - 1, m) % m;
    }
    long long modinv(long long a, long long m) {
        long long b = m, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= m;
        if (u < 0) u += m;
        return u;
    }
    long long comb(long long N,long long K,long long rest){
        long long res=kaijo[N]*modinv(kaijo[K],rest)%rest;
        res*=modinv(kaijo[N-K],rest);
        res%=rest;
        return res;
    }
};
int n,m,k;

signed main(){
  cin>>n>>m>>k;
  Nums lib(n+5);
  int res=m*lib.myPow(m-1,n-1,MOD);
  res%=MOD;
  rep1(i,k){
    int num=n-1-i;
    int buf=m;
    buf*=lib.myPow(m-1,num,MOD);
    buf%=MOD;
    buf*=lib.comb(n-1,i,MOD);
    buf%=MOD;
    res+=buf;
    res%=MOD;
  }
  cout<<res<<"\n";
  return 0;
}


Measured memory_bytes: 5368
#include <bits/stdc++.h>
#define N (long long)(1e9 + 7)
#define offset 2500
using namespace std;

long long n, k;
long long dp[55][55][5110] = {0};

long long solve();

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

long long solve() {
  dp[0][0][offset] = 1;
  for(int i = 1; i <= n; ++i) {
    for(int j = 0; j <= i; ++j)
      for(int m = offset - n * n; m <= offset + n * n;
          ++m) {
        dp[i][j][m] = dp[i - 1][j][m];
        // bring left
        // use left
        if(m - 2 * i >= 0)
          dp[i][j][m] += dp[i - 1][j + 1][m - 2 * i] *
                         (j + 1) % N * (j + 1) % N;
        dp[i][j][m] %= N;
        // bring left
        // use right
        dp[i][j][m] += dp[i - 1][j][m] * j % N;
        dp[i][j][m] %= N;
        // bring right
        // use left
        dp[i][j][m] += dp[i - 1][j][m] * j % N;
        dp[i][j][m] %= N;
        // bring right
        // use right
        if(m + 2 * i <= k + offset && j != 0)
          dp[i][j][m] += dp[i - 1][j - 1][m + 2 * i];
        dp[i][j][m] %= N;
      }
  }
  return dp[n][0][k + offset];
}


Measured memory_bytes: 110848
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Scanner;

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

    static class TaskB {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int x = in.nextInt();

            int maxValue = -1;

            for (int b = 1; b <= x; ++b) {
                for (int p = 2; p < 1000; ++p) {
                    int result = (int) Math.pow(b, p);
                    if (result > x) break;
                    maxValue = Math.max(result, maxValue);
                }
            }
            System.out.println(maxValue);
        }

    }
}



Measured memory_bytes: 23636
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>

auto& in = std::cin;
auto& out = std::cout;

int64_t K;
constexpr int32_t N = 50;
int64_t A[N];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> K;
	for (int32_t i = 0; i < N; ++i)
	{
		A[i] = (K / N) + (N - 1) + 1;
	}
	for (int32_t num = N - (K%N);num>=1; --num)
	{
		for (int32_t i = 0; i < N; ++i)
		{
			if (i == (num - 1)) {
				A[i] -= N;
			}
			else {
				++A[i];
			}
		}
	}

	out << N<<endl;
	out << A[0];
	for (int32_t i = 1; i < N; ++i)
	{
		out<<' '<<A[i];
	}
	out << endl;
	return 0;
}
#endif


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

int main() {
  int N, K;
  scanf("%d %d",&N,&K);
  int A[N];
  for (int i=0; i<N; i++) {
    scanf("%d",&A[i]);
  }
  int num_A[N];
  memset(num_A,0,sizeof(num_A));
  for (int i=0; i<N; i++) {
    num_A[A[i]-1]++;
  }
  sort(num_A,num_A+N,greater<int>());
  int ans=N;
  for (int i=0; i<K; i++) {
    ans-=num_A[i];
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 1792
import java.util.*;

class Main {
	static final int MOD = 998244353;
	Scanner sc;
	int N;
	int S;
	int[] dp;
	
	void calc() {
		sc = new Scanner(System.in);
		N = sc.nextInt();
		S = sc.nextInt();
		dp = new int[S+1];
		for (int i = 0; i < N; i++) {
			int a = sc.nextInt();
			dp[0] = i+1;
			if (a <= S) dp[S] = (int)( ( dp[S] + (long)dp[S-a]*(N-i) )%MOD);
			for (int j = S-a-1; j >= 0; j--) {
				dp[j+a] = (dp[j+a] + dp[j]) % MOD;
			}
		}
		System.out.println(dp[S]);
	}
	
	public static void main(String[] args) {
		new Main().calc();
	}
}


Measured memory_bytes: 40668
n,k,l=map(int,input().split())

#Union-Find
par=[-1 for i in range(n+1)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])
def f(a):
    if road[a]<0:
        return a
    else:
        return f(road[a])
def f2(a):
    if rail[a]<0:
        return a
    else:
        return f2(rail[a])
def size(a):
    return -par[root(a)]
def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(k):
    a=[int(j) for j in input().split()]
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])
import copy
road=copy.deepcopy(par)

par=[-1 for i in range(n+1)]

for i in range(l):
    r,s=[int(j) for j in input().split()]
    if root(r)!=root(s):
        connect(r,s)
import copy
rail=copy.deepcopy(par)
l=[(f(i),f2(i)) for i in range(1,1+n)]
from collections import Counter
c=Counter(l)
print(*(c[i] for i in l))







Measured memory_bytes: 49144
#include<bits/stdc++.h>
#define endl '\n'
#define mod 1000000007
typedef long long int ll;
using namespace std;
#define MAX 200005
int arr[MAX];
int dp[MAX][2];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n; cin>>n;
    string s; cin>>s;
    int cnt=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1') cnt++;
    }
    if(n==1 && cnt==1)  { cout<<0<<endl; return 0 ;} 
    arr[0]=0;
    for(int i=1;i<MAX;i++){
        bitset<33> bs(i);
        ll  md=bs.count();
        ll val=i%md;
        arr[i]=1+arr[val];
    }
    if(cnt-1!=0)
    {
        int x=cnt-1;
        dp[0][0]=1;
        for(int i=1;i<MAX;i++){
            dp[i][0]=(dp[i-1][0]*2)%x;
        }
    }
    int x=cnt+1;
    dp[0][1]=1;
    for(int i=1;i<MAX;i++){
        dp[i][1]=(dp[i-1][1]*2)%x;
    }
    ll ans1=0;
    ll ans2=0;
    for(int i=s.size()-1;i>=0;i--)
    {
        if(s[i]=='1') {
           if(cnt-1!=0) ans1=(ans1+dp[s.size()-1-i][0]) % (cnt-1) ; 
           ans2=(ans2+dp[s.size()-1-i][1])%(cnt+1);
        }
    }
    for(int i=0;i<s.size();i++){
        if(s[i]=='1')
        {
            int x=cnt-1;
            if(x==0) cout<<0<<endl;
            else{
                int pw=s.size()-1-i;
                ll val=dp[pw][0];
                ll fck=ans1;
                ans1-=val;
                ans1%=x;
                ans1+=x; ans1%=x;
                cout<<1+arr[ans1]<<endl;
                ans1=fck;
            }
        }
        else{
            int x=cnt+1;
            int pw=s.size()-1-i;
                ll val=dp[pw][1];
                ll fck=ans2;
                ans2+=val;
                ans2%=x;
                ans2+=x; ans2%=x;
                cout<<1+arr[ans2]<<endl;
                ans2=fck;
        }
    }
    
    
}

Measured memory_bytes: 6100
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;
  
#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
  
#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
  
const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
  long a[101];
  int n;
  
long func(long num,int wh,int flag){
	int i,j,k;
	if(n==wh){
		if(flag==1)return 3;
		else if(a[wh]%2==0)return 1;
		else return 2;
	}
	else{
	if(flag==1)return 3*func(num,wh+1,1);
		else{
			if(a[wh]%2==0){
				return func(num,wh+1,1)+2*func(num,wh+1,0);
			}else{
			return 2*func(num,wh+1,1)+func(num,wh+1,0);
			}
			
		}
	}
	return num;
}
  
  
int main(){
	int i,j;
	cin>>n;
	FORQ(i,1,n){
	cin>>a[i];
	}
	cout<<func(0,1,0)<<endl;
	
	
    return 0;
}

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

using namespace std;

#define endl '\n'

typedef long long int64;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
const int maxn = 100000 + 10;

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

    int n; cin >> n;

    long long answer = 0;
    long long rem = 0;

    for (int i = 0; i < n; ++i){
        long long v; cin >> v;

        if (rem && v){
            answer++;
            v--;
            rem--;
        }

        answer += v / 2;
        rem = v & 1;
    }

    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        // 入力(A B C)
        int a = sc.nextInt();
        String op = sc.next();
        int b = sc.nextInt();

        System.out.println((op.equals("+")) ? (a + b) : (a - b));
        sc.close();
    }
}


Measured memory_bytes: 35808
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    ans = 0
    dp = np.zeros(s+1,dtype=int)
    for j in range(n):
        dp[0] += 1
        aj = a[j]
        ndp = dp*1
        if s >= aj:
            dp[s-aj] *= (n-j)
        ndp[aj:] += dp[:-aj]
        ndp %= mod
        dp = ndp
    ans = (ans+dp[s]*(n-j))%mod
    print(ans)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 12516
fun main(args: Array<String>) {
  val (W, H, N) = readLine()!!.split(" ").map(String::toInt)
  var (left, right, bottom, top) = arrayOf(0, W, 0, H)
  for(i in 1..N){
    val (x, y, a) = readLine()!!.split(" ").map(String::toInt)
    when(a){
      1 -> left = max(x, left)
      2 -> right = min(x, right)
      3 -> bottom = max(y, bottom)
      4 -> top = min(y, top)
      else -> 0
    }
  }
  println(max((right-left),0)*max((top-bottom),0))
}
 
fun <T:Comparable<T>> max(a: T, b: T): T{
    return if(a<b) b else a
}
fun <T:Comparable<T>> min(a: T, b: T): T{
    return if(a>b) b else a
}

Measured memory_bytes: 37880
def linear(a, b, c, k):
  count = 0
  if(k>a):
    count+=a
    k-=a
    if(k>b):
      k-=b
      if(k>c):
        count-=c
      else:
        count-=k
    return count
  else:
    return k

a, b, c, k = map(int, input().split())
print(linear(a, b, c, k))


Measured memory_bytes: 9188
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;

const int V = 100005;
vector<int> to[V*2];
bool visited[V*2];    //グローバル変数なので０で初期化される

vector<int> cnt;

void dfs(int v){
    if(visited[v]) return;
    visited[v] = true;
    cnt[v/V]++;
    for(int u : to[v]) dfs(u);
}


int main(){
    int n; cin >> n;
   
    rep(i,n){
        int x,y;
        cin >> x >> y;
        y += V;
        to[x].push_back(y);
        to[y].push_back(x);
    }
    ll ans = 0;
    rep(i, V*2){
        if(visited[i]) continue;
        cnt = vector<int>(2);
        
        dfs(i);
        ans += (ll)cnt[0]*cnt[1];
    }
    ans -= n;
    cout << ans << endl;
    
    
    
}



Measured memory_bytes: 10240