akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;
struct edge{int to,cost;};

const int N = 1500;
const int INF = 19191919;
vector<edge> G[N];

int n;
int d[N][N];
bool can[N];

void dijkstra(int s)
{
    d[s][s] = 0;
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    pq.push({0,s});
    while(!pq.empty())
    {
        pi now = pq.top();
        pq.pop();
        int v = now.se;
        if(now.fi>d[s][v]) continue;
        for(const auto &e:G[v])
        {
            if(d[s][e.to] > d[s][v]+e.cost)
            {
                d[s][e.to] = d[s][v]+e.cost;
                pq.push({d[s][e.to],e.to});
            }
        }
    }
}

void check(int s, int D)
{
    queue<int> que;
    vector<bool> vis(n);

    rep(i,n)if(d[s][i]==D)
    {
        que.push(i);
        vis[i] = true;
    }

    while(!que.empty())
    {
        int v = que.front();
        que.pop();
        vis[v] = true;
        can[v] = false;

        for(const auto &e:G[v])
        {
            if(!vis[e.to] && d[s][e.to]==d[s][v]-e.cost)
            {
                vis[e.to] = true;
                que.push(e.to);
            }
        }
    }
}

int main()
{
    int r;
    cin >>n >>r;
    while(r--)
    {
        int s,t,w;
        cin >>s >>t >>w;
        --s; --t;
        G[s].pb({t,w});
        G[t].pb({s,w});
    }

    fill(d[0],d[N],INF);
    fill(can,can+N,true);
    rep(i,n) dijkstra(i);

    int max_d = 0;
    rep(i,n)rep(j,n) max_d = max(max_d,d[i][j]);

    rep(i,n) check(i,max_d);

    vector<int> ans;
    rep(i,n)if(can[i]) ans.pb(i);

    cout << ans.size() << endl;
    for(const int &i:ans) cout << i+1 << endl;
    return 0;
}

Measured memory_bytes: 12056
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 all = 0;
    if(b>=100){
    	all = a*1000+b;
    }else if (b>=10) {
		all = a*100+b;
    }else {
		all = a*10+b;
	}
    int cou = 0;
    for(int i=0; i<=all; i++) {
    	if(all == i*i) {
    	    cou++;
}
}
        if(cou>0){
    		System.out.println("Yes");
    	}else{
    		System.out.println("No");
      }
}
}


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

int main(){
  int N,M;
  int count=1;
  int MAX=0;
  cin>>N;
  vector<string> RED(N);
  for(int i=0;i<N;i++)
    cin>>RED.at(i);
  cin>>M;
  vector<string> BLUE(M);
  for(int i=0;i<M;i++)
    cin>>BLUE.at(i);
  
  for(int i=0;i<N;i++){
    for(int k=i+1;k<N;k++)
      if(RED.at(i)==RED.at(k))
          count++;
  	for(int j=0;j<M;j++)
    	if(RED.at(i)==BLUE.at(j))
          count--;
   MAX=max(count,MAX); 
    count=1;
  }
  
  if(MAX<0)
    cout<<0<<endl;
  else
    cout<<MAX<<endl;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

//-----------------------------------------------------------------------------

string n;
int ans;

int calc(string m) {
	int res=0;
	REP(i,(int)m.size()) res+=(m[i]-'0');
	return res;
}

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

	cin>>n;
	ans=calc(n);
	int tmp=0;
	REP(i,(int)n.size()) {
		int sum=tmp;
		sum+=(n[i]-'0')-1;
		FOR(j,i+1,(int)n.size()) sum+=9;
		ans=max(ans,sum);
		tmp+=(n[i]-'0');
		//cout<<"ans="<<ans<<",sum="<<sum<<",tmp="<<tmp<<endl;
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int N, K;
	char S[50];
	scanf("%d", &N); scanf("%d", & K);

	for (int i = 0; i <= N; i++) {
		scanf("%c", &S[i]);
		if (i == K) {
			if (S[i] == 'A')
				S[i] = 'a';
			else if (S[i] == 'B')
				S[i] = 'b';
			else if (S[i] == 'C')
				S[i] = 'c';
		}

		printf("%c", S[i]);
			
	}


	return 0;
}

Measured memory_bytes: 760
function Main (input) {
  input = input.split("\n");
  if(input[input.length - 1] === "") 
  {
    input.pop();
  }
  var min = 10;
  var total = 0;
  for(var i = 0; i < input.length; i++) {
    var r = input[i] % 10;
    if(r > 0 && r < min){
      min = r;
    }
    total += (Math.ceil(input[i] /10) * 10);
  }
  if ( min < 10) {
    total = total - 10 + min;
  }
  console.log(total);
}

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


Measured memory_bytes: 7372
#include<iostream>
using namespace std;
#define PI 3.141592653589

int main()
{
	int i,j,H,W;
	while(1)
	{
		cin >> H >> W ;
		if((H == 0)&& (W == 0)) break;

		for(i=0;i<H;i++)
		{
			for(j=0;j<W;j++)
			{
				if((i==0)||(j==0)||(i==(H-1))||(j==(W-1)))
				{
					cout << '#' ;
				}

				else
				{
					cout << '.' ;
				}
			}
			cout << endl ;
		}

		cout << endl ;

	}

	return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    string S, T;
    cin >> S >> T;

    string U = "UNRESTORABLE";
    if(SZ(S) >= SZ(T)) {
        REP(i,0,SZ(S)-SZ(T)+1) {
            bool f = true;
            REP(j,i,i+SZ(T)) {
                if(S[j] != '?') {
                    if(S[j] != T[j-i]) {
                        f = false;
                        break;
                    }
                }
            }
            if(f) {
                U = S;
                REP(j,i,i+SZ(T)) U[j] = T[j-i];
            }
        }
        REP(i,0,SZ(U)) {
            if(U[i] == '?') U[i] = 'a';
        }
    }
    PR(U);
    
    return 0;
}

/*



*/

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

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

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

const int dx[] = {0, -1, 1, 0};
const int dy[] = {-1, 0, 0, 1};

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    int n;
    cin >> n;
    vector< int > v(n);
    for( int i = 0; i < n; ++i ) {
        cin >> v[i];

    }

    int mn = INF;
    for( int i = 1; i <= 100; ++i ) {
        int t = 0;
        for( int j = 0; j < n; ++j ) {
            t += (v[j] - i) * (v[j] - i);

        }
        mn = min(t, mn);

    }
    cout << mn << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int

using namespace std;

int main(){
  ll n;
  cin >> n;
  ll a[n],b[n],c[n];
  for(ll i = 0;i < n;i++){
  	cin >> a[i] >> b[i] >> c[i];
  }
  ll dp[n + 1][3];
  dp[0][1] = 0;
  dp[0][2] = 0;
  dp[0][0] = 0;
  for(ll i = 1;i <= n;i++){
  	dp[i][0] = max(dp[i - 1][1],dp[i - 1][2]) + a[i - 1];
    dp[i][1] = max(dp[i - 1][0],dp[i - 1][2]) + b[i - 1];
    dp[i][2] = max(dp[i - 1][0],dp[i - 1][1]) + c[i - 1];
  }
  cout << max(dp[n][0],max(dp[n][1],dp[n][2]));
  return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

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


int main(int argc, char const *argv[])
{
	int q;
	int n;
	string s;
	int max;
	int cnt;

	cin>>q;

	for(int i1=0;i1<q;i1++){
		cin>>n;

		cnt=0;
		while(1){
			if(n/10==0) break;

			s=toString<int>(n);

			max=0;
			for(int i2=1;i2<s.size();i2++){
				int temp=(toInt(s.substr(0,i2)))*(toInt(s.substr(i2,s.size()-i2)));
				if(max<temp) max=temp;
			}
			n=max;
			cnt++;
			if(cnt>1000000) break;
		}
		if(cnt>1000000) cout<<-1<<endl;
		else cout<<cnt<<endl;

	}
	return 0;
}

Measured memory_bytes: 1232
sx, sy, tx, ty = map(int, input().split())

ans = 'R' * (tx - sx) + 'U' * (ty - sy)
ans += 'L' * (tx - sx) + 'D' * (ty - sy)
ans += 'L' + 'U' * (ty - sy + 1) + 'R' * (tx - sx + 1) + 'D'
ans += 'R' + 'D' * (ty - sy + 1) + 'L' * (tx - sx + 1) + 'U'
print(ans)


Measured memory_bytes: 61252
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define fi first
#define se second
#define db double
#define eb emplace_back
#define PI acos(-1.0)
#define ll long long int
#define pii pair<int,int>
#define sz(a) (int)(a).size()
#define bug printf("!!!!!!\n");
#define ull unsigned long long int
#define Fill(x,y) memset(x,y,sizeof(x))
using namespace std;
const db eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll INF = 1e18;
const int mod = 1e9+7;
const int maxn = 5e5+5;
struct node {
    int to, next, w;
    bool operator < (const node &_) const {
        return w == _.w ? to < _.to : w > _.w;
    }
}e[maxn<<1];
int cnt, head[maxn];
void add(int u, int v, int w) {
    e[cnt] = node{v, head[u], w};
    head[u] = cnt++;
}
int n, m;
set<int>S[maxn];
void init() {
    cnt = 0 ; Fill(head, -1);
    for (int i = 1 ; i <= n ; i ++) {
        S[i].clear();
    }
}
bool vis[maxn]; int dis[maxn];
void dij(int st, int ed) {
    priority_queue<node> q;
    Fill(vis,0); Fill(dis, inf);
    q.push(node{st, 0, 0}); dis[st] = 0;
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if(vis[u.to]) continue;
        vis[u.to] = 1;

        for (int i = head[u.to]; ~i; i = e[i].next) {
            int to = e[i].to;
            int w = S[u.to].count(e[i].w) ? 0 : 1;
            if (dis[to] > dis[u.to] + w) {
                dis[to] = dis[u.to] + w;
                q.push(node{to, 0, dis[to]});
                S[to].clear();
                S[to].insert(e[i].w);
            }
            else if(dis[to] == dis[u.to] + w) S[to].insert(e[i].w);
        }
    }
    printf("%d\n", dis[ed] == inf ? -1:dis[ed]);
}
void solve() {
    while(~scanf("%d%d", &n, &m)) {
        init();
        for (int i = 1 ; i <= m ; i ++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w); add(v, u, w);
        }
        dij(1, n);
    }
}
int main() {
    //  freopen("out.txt","w",stdout);
    int t = 1, cas = 1;
    //scanf("%d",&t);
    while(t--){
        //printf("Case #%d: ", cas++);
        solve();
        //printf("\n");
    }
}

//#include <unordered_map>


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

using ll=long long; 

void solve(){
	string s;
	cin>>s;
	if(int(s.size())%2==1){
		s.pop_back();
	}
	else{
		s.pop_back();
		s.pop_back();
	}
	while(1){
		if(s.substr(0,s.size()/2)==s.substr(s.size()/2,s.size()/2)){
			cout<<s.size()<<endl;
			return;
		}
		s.pop_back();
		s.pop_back();
	}
}

signed main(){
	//while(1)
	solve();
}

Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = int64_t;
using ull = uint64_t;

constexpr ll INF = numeric_limits<ll>::max() / 4;
namespace utils{
    template<class T, class Compare> using p_queue = priority_queue<T, vector<T>, Compare>;
    template<class T> using min_queue = p_queue<T, greater<T>>;
    template<class T> using max_queue = p_queue<T, less<T>>;

    template<class T> bool min_update(T& X, const T& A){ if(X > A) {X = A; return true;} return false; }
    template<class T> bool max_update(T& X, const T& A){ if(X < A) {X = A; return true;} return false; }
    using V_Set = unordered_set<int>;
    using E_Set = unordered_map<int, V_Set>;

#define ALL(x) begin(x), end(x)
#define rALL(x) rbegin(x), rend(x)
}
using namespace utils;


void sub_main(istream &is) {
    ll N;
    is >> N;
    if(!is) return;
    vector<int> A(N);
    for (auto &&a : A) {
        is >> a;
    } // end a
    vector<int> in(N);
    int sum = 0;
    for (int i = N; i > 0; i--) {
        int parity = 0;
        for (int j = i+i; j <= N; j+=i) {
            parity = parity ^ in[j-1];
        } // end j
        if(parity ^ A[i-1]) {
            in[i-1] = 1;
            sum++;
        }

    } // end i

    cout << sum << endl;
    for (int k = 0; k < N; ++k) {
        if(in[k] == 1)
            cout << k+1 << " ";
    } // end k
    cout << endl;

}

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef DEBUG
    string test_cases = "test_D.txt";
    cerr << "DEBUG MODE" <<  endl;
    cerr << test_cases << " -->" << endl;
    auto fs = fstream(test_cases, fstream::in);
    int lp = 0;
    while(fs) {
        lp++;
        cout << lp <<  "#------\n";
        sub_main(fs);
    }
    cout << "------#" << endl;
    if(lp <= 1) sub_main(cin);
#else
    sub_main(cin);
#endif
    return 0;
}


Measured memory_bytes: 2560
R = lambda: list(map(int, input().split()))
h, w = R()
s = [input() for i in range(h)]

# h, w = 4, 6
# s = ["#..#..",".....#","....#.","#.#..."]
s_ = [list(x) for x in zip(*s)]

ho = [[0]*w for i in range(h)]
he = [[0]*h for i in range(w)]

for j,str in enumerate(s):
    count = 0
    col = 0
    for i, eachstr in enumerate(str):
        if eachstr == "#":
            if i == 0:
                pass
            else:
                for k in range(col,i):
                    ho[j][k] = count
            col = i + 1
            count = 0
        else:
            count += 1
    else:
        if col < w:
            for k in range(col,i+1):
                ho[j][k] = count

for j,str in enumerate(s_):
    count = 0
    col = 0
    for i, eachstr in enumerate(str):
        if eachstr == "#":
            if i == 0:
                pass
            else:
                for k in range(col,i):
                    he[j][k] = count
            col = i + 1
            count = 0
        else:
            count += 1
    else:
        if col < w:
            for k in range(col,i+1):
                he[j][k] = count

he_ = [list(x) for x in zip(*he)]

ans = 0
for i,j in zip(ho,he_):
    for ss, tt in zip(i,j):
        ans = max(ans, ss+tt)
print(ans-1)

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

struct UnionFind {
    vector<int> par;

    UnionFind(int N) : par(N) {
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(void)
{
    long long N, M;
    cin >> N >> M;
    vector<long long> p(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> p[i];
    }
    vector<long long> x(M);
    vector<long long> y(M);
    for (long long i = 0; i < M; i++)
    {
        cin >> x[i] >> y[i];
    }

    UnionFind tree(N+1);
    for (long long i = 0; i < M; i++)
    {
        tree.unite(x[i], y[i]);
    }
    long long ans = 0;
    for (long long i = 0; i < N; i++)
    {
        if (tree.same(i+1, p[i]))
        {
            ans++;
        }
    }
    cout << ans << endl;
}

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

using namespace std;

long long inf=1000000007;

int main(){
	int n;
	cin>>n;
	vector<pair<int,int>> hoge;

	int pre=inf;
	int j=0;
	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		if(tmp!=pre){
			hoge.push_back(make_pair(tmp,j));
			j++;
		}
		pre=tmp;
	}

	if(hoge.size()==1){
		if(hoge.at(0).first>0) cout<<1<<endl;
		else cout<<0<<endl;
		return 0;
	}

	vector<pair<int,int>> fuga=hoge;
	sort(fuga.begin(),fuga.end());
	reverse(fuga.begin(),fuga.end());

	int ans=-1;
	int cnt=0;
	int bef=inf;

	for(auto a:fuga){
		if(a.first==0) break;
		if(a.first!=bef) ans=max(ans,cnt);
		bef=a.first;

		if(a.second>0 && a.second<j-1){
			if(a.first>hoge.at(a.second-1).first && a.first>hoge.at(a.second+1).first) cnt++;
			else if(a.first<hoge.at(a.second-1).first && a.first<hoge.at(a.second+1).first) cnt--;
		}else if(a.second==0){
			if(a.first>hoge.at(a.second+1).first) cnt++;
		}else if(a.second==j-1){
			if(a.first>hoge.at(a.second-1).first) cnt++;
		}
	}

	ans=max(ans,cnt);

	cout<<ans<<endl;

	return 0;
}



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

using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n+1];
    int b[n];

    for(int i=0;i<n+1;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }

    long long int c=0;
    for(int i=0;i<n;i++){
        c+=min(a[i],b[i]);
        c+=min(a[i+1],max(a[i],b[i])-a[i]);
        a[i+1]=a[i+1]-min(a[i+1],max(a[i],b[i])-a[i]);
    }
    cout<<c<<endl;
}

Measured memory_bytes: 1024
#include <vector>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
bool is_prime(int n, int k = 3)
{
    if(n < k * k) { return true; }
     
    if(n % k == 0) { return false; }
     
    return is_prime(n, k + 2);
}
 
int main()
{
    vector<int> prime = {2};
     
    for(int i = 3; i < 101300; i += 2)
    {
        if(is_prime(i))
        {
            prime.push_back(i);
        }
    }
     
    int n, m;
     
    while(true)
    {
        scanf("%d", &n);
        scanf("%d", &m);
         
        if(n == -1 && m == -1) { break; }
         
        int ptr = distance(prime.begin(), lower_bound(prime.begin(), prime.end(), n + 1));
         
        vector<int> c; int r = min(22, max(m / 2, 12)) - 1;
        
        for(int i = ptr + r; i >= ptr; i--)
        {
            for(int j = ptr + r; j >= i; j--)
            {
                c.push_back(prime[i] + prime[j]);
            }
        }
        
        sort(c.begin(), c.end());
         
        printf("%d\n", c[m - 1]);
    }
     
    return 0;
}

Measured memory_bytes: 3320
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

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

int main() {

    int A, B, C;
    cin >> A >> B >> C;

    int M = max(A, max(B, C));

    int count = 0;

    if (M * 3 % 2 != (A + B + C) % 2) M++;

    count += (M - A) / 2;
    count += (M - B) / 2;
    count += (M - C) / 2;
    if ((M - A) % 2 == 0 && (M - B) % 2 == 0 && (M - C) % 2 == 0) cout << count << endl;
    else cout << count + 1 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int gcd(int x,int y)
{
	return y>0?gcd(y,x%y):x;
}

int lcm(int x,int y)
{
	return x/gcd(x,y)*y;
}

int main(void)
{
	int x,y;

	while(scanf("%d %d",&x,&y)!=EOF) {
		printf("%d %d\n",gcd(x,y),lcm(x,y));
	}
	return 0;
}

Measured memory_bytes: 596
#include"bits/stdc++.h"
using namespace std;
const int N=1e6+4;
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	freopen("out","w",stdout);
	#endif

	int k;
	cin>>k;

	
	
	int cur=0;int rem;
	for(int i=1;i<=N;i++)
	{
		cur=cur*10+7;
		rem=cur%k;
		if(rem==0){cout<<i;return 0;}
		cur=rem;
	}
	cout<<-1;

	
}

Measured memory_bytes: 3632
#!/usr/bin/env python3
#ABC134 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]

x = [float('inf') for _ in range(n)]
for i in range(n)[::-1]:
    r = bisect.bisect_right(x,a[i])
    x[r] = a[i]
cnt = x.count(float('inf'))
print(n-cnt)


Measured memory_bytes: 50652
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,t=map(int,input().split())
    A=list(map(int,input().split()))
    S=[None]*n
    S[-1]=A[-1]
    for i in range(n-2,-1,-1):
        S[i]=max(A[i],S[i+1])
    d=max(S[i+1]-A[i] for i in range(n-1))
    print(sum(1 for i in range(n-1) if(S[i+1]-A[i]==d)))
resolve()

Measured memory_bytes: 62704
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
using namespace std;

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

int main() {
    int N;
    cin >> N;
    int now_H = 0;
    int count = 0;
    for (int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        if (now_H <= temp) count++;
        now_H = max(now_H, temp);
    }
    cout << count << endl;
    return 0;
}

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

int main(){
  int N, ans;
  ans = 0;
  string S;
  cin >> N >> S;
  for(int i = 0; i < N - 2; i++){
    if(S.at(i) == 'A'){
      if(S.at(i + 1) == 'B'){
          if(S.at(i + 2) == 'C') ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
    string s;
    cin >> s;
    int n = (int)s.size();
    
    if ((s.at(0) == '0') || (s.at(n - 1)) == '1') {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 0; i < n / 2; i++) {
        if (s.at(i) != s.at(n - i - 2)) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    int p = 1;
    int v = 2;
    for (int i = 0; i < n - 1; i++) {
        cout << p << " " << v << endl;
        if (s.at(i) == '1') p = v;
        v++;
    }
}

Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

bool f[4];
ll sum;
string s;

ll changei(string s){
	stringstream ss;
	ll a;
	ss << s;
	ss >> a;
	return a;
}

int main(){
	cin >> sum;
	while (cin >> s){
		ll a;
		if (s == "+") f[0] = 1;
		else if (s == "-") f[1] = 1;
		else if (s == "*") f[2] = 1;
		else if (s == "/") f[3] = 1;
		else if (s == "="){
			cout << sum << endl;
			sum = 0;
			break;
		}
		else{
			a = changei(s);
			if (f[0])sum += a;
			if (f[1])sum -= a;
			if (f[2])sum *= a;
			if (f[3])sum /= a;
			REP(i, 4)f[i] = 0;
		}
	}
}

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

using namespace std;

int main()
{
    int N,sum=0,a;
    cin>>N;
    for(int i=1; i<=N; i++)
    {
        cin>>a;
        if(i%2!=0&&a%2!=0)
            sum++;
    }
    cout<<sum<<endl;
    return 0;
}


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

int selectionSort(int A[], int n){
	int sw = 0;
	for(int i = 0; i < n; i++){
		int minij = i;
		for(int j = i;  j < n;  j++){
			if(A[minij] > A[j]){
				minij = j;
			}
		}
		if(A[i] > A[minij]){
			swap(A[i], A[minij]);
			sw = sw + 1;
		}
	}
	return sw;
}

int main(){
	int n;
	int A[100];
	cin >> n;
	for(int i = 0; i < n; i++) cin >> A[i];
	
	int count = selectionSort(A, n);
	for(int i = 0; i < n; i++){
		if(i) cout << " ";
		cout << A[i];
	}
	cout << endl;
	cout << count << endl;
	
	return 0;
}

Measured memory_bytes: 1160
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
S = [int(s) for s in input()] + [1]

l = 0
r = -1
ans = 0
cnt = 0
tmp = ""
used = [0]*(N + 1)
for l in range(N):
    if S[l] + S[l-1] == 0:
        continue
    while r < N and used[r] - used[l-1] <= K:
        r += 1
        if S[r]:
            used[r] = used[r - 1]
        else:
            if S[r-1]:
                used[r] = used[r - 1] + 1
            else:
                used[r] = used[r - 1]
    ans = max(ans, r-l)

print(ans)


Measured memory_bytes: 8260
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        int re=s[i];
        re=re+n;

        if(re>90 && (s[i]>='A' && s[i]<='Z'))
        {
            re=re-26;
        }
        char a=re;
        cout<<a;
    }
    return 0;


}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<P,int>P2;
vector<P2>v1,v2;
void solve(){
  int n,sum=0,ans=0;
  cin>>n;
  int a[n+1];
  r(i,n)cin>>a[i],sum+=a[i];
  if(n<=2){
    cout<<a[n-1]<<endl;
    return ;
  }
  a[n]=0;
  v1.clear();
  v2.clear();
  v1.push_back(P2(P(a[0],a[1]),a[2]));
  r(l,n-2){
    set<P2>s;
    r(o,v1.size()){
      int i=v1[o].first.first;
      int j=v1[o].first.second;
      int k=v1[o].second;
      if(j){
        P2 p=P2(P(j-1,k+i),a[l+3]);
        if(!s.count(p)){
          v2.push_back(p);
          s.insert(p);
        }
      }
      if(k){
        P2 p=P2(P(0,k-1),a[l+3]+j);
        if(!s.count(p)){
          v2.push_back(p);
          s.insert(p);
        }
      }
      P2 p=P2(P(j,k),a[l+3]);
      if(!s.count(p)){
        v2.push_back(p);
        s.insert(p);
      }
    }
    v1=v2;
    v2.clear();
  }
  r(o,v1.size()){
    int j=v1[o].first.second;
    ans=max(j,ans);
  }
  cout<<ans<<endl;
}
int main(){
  int TEST;
  cin>>TEST;
  while(TEST--)solve();
}


Measured memory_bytes: 3228
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>

using namespace std;

struct node {
	int per, sib, left, right, deg, dep, hei, typ;
};

void bfs(int x, vector<node> &nd) {
	queue<int> q;
	q.push(x);
	nd[x].dep = nd[x].typ = 0;
	
	while (!q.empty()) {
		int k = q.front(); q.pop();
		int l = nd[k].left, r = nd[k].right;
		if (l != -1) {
			q.push(l);
			nd[l].dep = nd[k].dep + 1;
		}
		if (r != -1) {
			q.push(r);
			nd[r].dep = nd[k].dep + 1;
		}
	}
}

int main() {
	int n, st, start = 0;
	cin >> n;
	vector<node> nd(n);
	vector<string> type(3);
	type[0] = ", root";
	type[1] = ", internal node";
	type[2] = ", leaf";
	for (int i = 0; i < n; i++) nd[i].per = nd[i].sib = -1;
	for (int i = 0; i < n; i++) {
		int id, left, right, deg = 0;
		cin >> id >> left >> right;
		nd[id].left = left;
		nd[id].right = right;
		if (left != -1) {
			nd[left].per = id;
			nd[right].sib = left;
			deg++;
		} 
		if (right != -1) {
			nd[right].per = id;
			nd[left].sib = right;
 			deg++;
		}
		nd[id].deg = deg;
		if (deg) nd[id].typ = 1;
		else nd[id].typ = 2;
	}
	for (int i = 0; i < n; i++) {
		if (!nd[i].deg) {
			st = i;
			while (nd[st].per != -1) {
				if (nd[nd[st].per].hei >= nd[st].hei + 1) break;
				else nd[nd[st].per].hei = nd[st].hei + 1;
				st = nd[st].per;
			}
			if (nd[st].per == -1) start = st;
		}
	}
	bfs(start, nd);
	for (int i = 0; i < n; i++) {
		cout << "node " << i << ": parent = " << nd[i].per << ", sibling = " << nd[i].sib << ", degree = " << nd[i].deg;
		cout << ", depth = " << nd[i].dep << ", height = " << nd[i].hei << type[nd[i].typ] << endl;
	}
}

//node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node

Measured memory_bytes: 3228
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
ll MOD = 1000000007;
//ll INF = 21474836470000000;
ll INF = 100100100100100100;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    vector<ll> index(N);
    rep(i,N){
        cin >> A[i];
        A[i]--;
        index[A[i]] = i;
    }
    set<ll> st;
    ll ans = 0;
    rrep(i,N){
        ll x = index[i];
        st.insert(x);
        vector<ll> L(2),R(2);
        L[0] = -1;L[1] = -1;R[0] = N;R[1] = N;
        auto itr = st.find(x);
        rep(j,2){
            if(itr == st.begin())break;
            itr--;
            L[j] = *itr;
        }
        itr = st.find(x);
        rep(j,2){
            itr++;
            if(itr == st.end())break;
            R[j] = *itr;
        }
        ans += (i+1) * ((R[1] - R[0])*(x - L[0]) + (R[0] - x)*(L[0] - L[1]));
    }
    cout << ans << endl;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define FIN         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ii          pair<int,int>
#define F           first
#define S           second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define rall(x)     (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a)   for(int i = a; i >= 0; i--)
#define fori(i,m)   for(auto i = m.begin(); i != m.end(); i++) 
#define w(t)        while(t--)
#define sz(s)       int(s.size())
#define cls(a,car)  memset(a,car,sizeof (a))
#define db(x)       cerr << #x << " is " << x << '\n'
#define FL          freopen("in", "r", stdin),freopen("out", "w", stdout);
#define EjecuteTime cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"
#define angle(x)    double(x * acos(-1) / 180.0)
using namespace std;
typedef long long   ll;
typedef vector<int> vi;
typedef vector<ii>  vii;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const double E = 1e-9;
int dx[] = {1, 0}, dy[] = {0, 1};
//int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
// fflush(stdout)
// cout << flush
// a + b = a ^ b + 2 * (a & b)
int n;
ll W;
ll dp[101][100010];
ll w[101];
int  v[101];
ll f(int i, int want){
    if(i == n){
        if(want == 0)
            return 0;
        return 1e12;
    }
    ll &ans = dp[i][want];
    if(ans != -1)return ans;
    ans = 1e12;
    if(want >= v[i])
    ans = min(f(i + 1, want - v[i]) + w[i], ans);
    ans = min(f(i + 1, want), ans);
    return ans;
} 
int main(){
    //FL;
    FIN;
    cin >> n >> W;
    ll sum = 0;
    fore(i, 0, n){
        cin >> w[i] >> v[i];
        sum += v[i];
    }
    cls(dp, -1);
    int ans = 0;
    fore(i, 1, sum + 1){
        ll cur = f(0, i);
        if(cur <= W)
            ans = i;
    }
    cout << ans << '\n';
    EjecuteTime;
    return 0;
}       

Measured memory_bytes: 82736
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, M;
    double p = 0;   //predict

    cin >> N >> M;

    vector<int> A(N);

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

    p /= 4 * M;

    int c = count_if(A.begin(), A.end(),
                     [p](int a) -> bool { return a >= p; });

    if (c >= M)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<vector>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define eps (1e-10)
#define equals(a,b) (fabs((a)-(b)) < eps)
#define all(n) (n).begin(),(n).end()
#define inf (1<<29)
 
using namespace std;
typedef long double ld;
 
struct P
{
  ld left,right,weight;
  P(ld left=0,ld right=0,ld weight=inf):left(left),right(right),weight(weight){}
  bool operator < (const P& a)const
  {
    if(!equals(weight,a.weight))return weight < a.weight;
    if(!equals(left,a.left))return left < a.left;
    return right < a.right;
  }
};
 
ld r,ans;
int s;
 
bool check(ld v)
{
  if(equals(v,r) || v > r)return false;
  return true;
}
 
P unit(P a,P b)
{
  P node;
  node.weight = a.weight + b.weight;
  ld middle = b.weight/(a.weight+b.weight);
  node.left = min(-b.weight/(a.weight+b.weight) + a.left,b.left + (1-middle));
  node.right = max(a.weight/(a.weight+b.weight) + b.right,a.right - middle);
  return node;
}
 
void dfs(vector<P> vec)
{
  int n = vec.size();
  if(n <= 1)
    {
      ld len = vec[0].right - vec[0].left;
      assert(equals(len,0) || len > 0);
      if(check(len))ans = max(ans,len);
      return;
    }
  
  rep(i,n)
    {
      rep(j,n)
	{
	  if(i == j)continue;
	  vector<P> nvec;
	  rep(k,n)
	    if(k == i || k == j)continue;
	    else                nvec.push_back(vec[k]);
	  P p = unit(vec[i],vec[j]);
	  nvec.push_back(p);
	  dfs(nvec);
	}
    }
}
 
 
int main()
{
  /*
  rep(i,100000)
    {
    P a,b;
      cout << "type node a\n";
      cin >> a.left >> a.right >> a.weight;
      cout << "type node b\n";
      cin >> b.left >> b.right >> b.weight;
      P c = unit(a,b);
      cout << "unit c (" << c.left << "," << c.right << "," << c.weight << ")" << endl;
    }
  */
  int T;
  while(cin >> T)
    {
      while(T--)
	{
	  cin >> r;
	  cin >> s;
	  vector<P> ps(s);
	  rep(i,s)cin >> ps[i].weight;
	  
	  ans = -inf;
	  
	  dfs(ps);
	  
	  if(equals(ans,-inf))cout << -1 << endl;
	  else                cout << setiosflags(ios::fixed) << setprecision(9) << ans << endl;
	  
	}
    }
  return 0;
}

Measured memory_bytes: 1300
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const int INF = -100100100;
typedef pair<int,int> P;

int main(){
    string s, so;
    cin >> s;
    so = s;
    int n = s.size();
    reverse(s.begin(), s.end());
    string sr = s;
    bool ans = true;
    if(so != sr)ans = false;
    string ss;
    ss = so.substr(0,(int)(n-1)/2);
    string sso = ss;
    reverse(ss.begin(), ss.end());
    if(sso != ss)ans = false;
    string sss;
    sss = so.substr((int)(n+3)/2 -1);
    string ssso = sss;
    reverse(sss.begin(), sss.end());
    // cout << ssso << endl;
    // cout << sss  << endl;
    
    if(ssso != sss)ans = false;
    if(ans){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }


    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
		int x = 0,y = 0;
		if(a > c) {
			y = a;
			a = c;
			c = y;
			y = b;
			b = d;
			d = y;
		}
		if(b < c) {
			System.out.println(x);
		}else if(b < d ){
			x = (b - c);
			System.out.println(x);
		}else{
			x = (d - c);
			System.out.println(x);
		}
	}
}



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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

// ------------------------------------------------------------------------------------------

int N, W;
int v[111], w[111];
int dp[111][111111];

void solve() {
   rep (i, N) {
      for (int j = 0; j <= W; j++) {
         dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
         if (j + w[i] <= W) {
            dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j]+v[i]);
         }
      }
   }
   cout << dp[N][W] << endl;
}

int main() {
   cin >> N >> W;
   rep (i, N) { cin >> v[i] >> w[i]; }

   solve();

   return 0;
}


Measured memory_bytes: 7396
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 400000
#define MAXM 1000000
#define INF 1000000000
int n,m,S,T;
int head[MAXN+5],cur[MAXN+5];
int dep[MAXN+5],ecnt,a[MAXN+5],b[MAXN+5];
int cnt1,cnt2,k1[MAXN+5],k2[MAXN+5];
int read(){
	int F=1,x=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*F;
}
void Init(){
	ecnt=1;memset(head,-1,sizeof(head));
}
struct edge{
	int to,nxt,cap;
}e[MAXM*2+5];
void add(int u,int v,int cap,int tp){
	e[++ecnt]=(edge){v,head[u],cap};
	head[u]=ecnt;
	if(tp)e[++ecnt]=(edge){u,head[v],cap};
	else e[++ecnt]=(edge){u,head[v],0};
	head[v]=ecnt;
}
int BFS()
{
    for(int i=S;i<=T;i++)dep[i]=0,cur[i]=-1;
    queue<int> Q;
    Q.push(S);
    dep[S]=1;
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();
        for(int i=head[x];i!=-1;i=e[i].nxt)
        {
            int xnt=e[i].to;
            if(dep[xnt]||!e[i].cap)continue;
            dep[xnt]=dep[x]+1;
            Q.push(xnt);
        }
    }
    return dep[T];
}
int dinic(int x,int Flow)
{
    if(x==T)return Flow;
    int pcap=Flow;
    if(cur[x]==-1)cur[x]=head[x];
    for(int &i=cur[x];i!=-1;i=e[i].nxt)
    {
        int xnt=e[i].to;
        if(dep[x]+1!=dep[xnt]||!e[i].cap)continue;
        int pe=dinic(xnt,min(e[i].cap,pcap));
        e[i].cap-=pe,e[i^1].cap+=pe;
        pcap-=pe;
        if(!pcap)break;
    }
    if(pcap)dep[x]=-1;
    return Flow-pcap;
}
int main(){
	Init();
	n=read();
	for(int i=1;i<=n;i++)a[i]=read()+1;
	for(int i=1;i<=n;i++)b[i]=read()+1;
	for(int i=1;i<=n;i++)
	if(!k1[i]){
		cnt1++;int x=i;
		do{
			k1[x]=cnt1;
			x=a[x];
		}while(x!=i);
	}
	for(int i=1;i<=n;i++)
	if(!k2[i]){
		cnt2++;int x=i;
		do{
			k2[x]=cnt2;
			x=b[x];
		}while(x!=i);
	}
	S=0,T=cnt1+cnt2+1;
	int ans=n;
	for(int i=1;i<=n;i++){
		if(a[i]==i&&b[i]==i)ans--;
		else if(a[i]==i)add(S,k2[i]+cnt1,1,0);
		else if(b[i]==i)add(k1[i],T,1,0);
		else{
			if(a[i]==b[i])add(k2[i]+cnt1,k1[i],1,1);//显然只会割其中的一条
			else add(k1[i],k2[i]+cnt1,1,0);
		}
	}
	while(BFS())ans-=dinic(S,INF);
	printf("%d",ans);
}

Measured memory_bytes: 18176
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;


int main() {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());

    s += '0';
    int n = s.size();
    vector<vector<ll>> dp(n + 2, vector<ll>(2, INF));
    dp[0][0] = 0;
    rep(i, n + 1) {
        rep(j, 2) {
            int x = s[i] - '0';
            x += j;
            rep(a, 10) {
                int ni = i + 1, nj = 0;
                int b = a - x;
                if (b < 0) {
                    nj = 1;
                    b += 10;
                }
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b);
            }
        }
    }
    int ans = dp[n][0];
    cout << ans << endl;
}


Measured memory_bytes: 55940
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <map>
#include <cstdlib>
#include <vector>


using namespace std;

int n;
 int a[100];

int MAX(){
	int ans=-1000000000;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			int m=abs(a[i]-a[j]);
		
			ans=max(m,ans);
		}
	}

	return ans;
}

int main()
{
	
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	
	cout<<MAX()<<endl;
	return 0;
}

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

long long int mod=1e9+7;

int main(){
  string s;
  cin>>s;
  vector<vector<long long int> > dp(s.size()+1,vector<long long int>(4,0));
  dp[0][0]=1;
  for(int i=0;i<s.size();i++){
    for(int j=0;j<4;j++){
      if(s[i]=='?'){
        dp[i+1][j]+=dp[i][j]*3;
        dp[i+1][j]%=mod;
      }else{
        dp[i+1][j]+=dp[i][j];
        dp[i+1][j]%=mod;
      }
    }
    for(int j=0;j<3;j++){
      if(j==0&&(s[i]=='A'||s[i]=='?')){
        dp[i+1][1]+=dp[i][0];
        dp[i+1][1]%=mod;
      }
      if(j==1&&(s[i]=='B'||s[i]=='?')){
        dp[i+1][2]+=dp[i][1];
        dp[i+1][2]%=mod;
      }
      if(j==2&&(s[i]=='C'||s[i]=='?')){
        dp[i+1][3]+=dp[i][2];
        dp[i+1][3]%=mod;
      }
    }
  }

  cout<<dp[s.size()][3]%mod<<endl;
}


Measured memory_bytes: 7424
from operator import mul
from functools import reduce
from math import factorial

def cmb(n,r):
  r=min(n-r,r)
  if r == 0: return 1
  over=reduce(mul,range(n,n-r,-1))
  under=reduce(mul,range(1,r+1))
  return over//under

n,p,*a=map(int,open(0).read().split())
b=[i for i in a if i%2==0]
c=[i for i in a if i%2==1]
ans=0
x=0
for s in range(len(b)+1):
  x+=cmb(len(b),s)
if p==0:
  for s in range(0,len(c)+1,2):
    ans+=x*cmb(len(c),s)
  print(ans)
else:
  for s in range(1,len(c)+1,2):
    ans+=x*cmb(len(c),s)
  print(ans)

Measured memory_bytes: 3572
#include<iostream>
#include<cmath>
using namespace std;
int main(){
  long long n,a,b;
  cin >> n >> a >> b;
  long long m = min((a+b-1)/2,n+(-a-b+1)/2);
  if((b-a) %2==1)cout << m<<endl;
  else cout << min(m,(b-a)/2)<<endl;
  return 0;
}


Measured memory_bytes: 256
# B Popular Vote

N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse = True)
border = sum(A) / (4 * M) 
cnt = 0
for a in A:
  if a >= border:
    cnt += 1
  else:
    break

if cnt >= M:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 9060
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<limits.h>
#include<string>
#include<iomanip>
#include<numeric>
#include<queue>
using namespace std;

long long  mod = 1000000007;

long max(long x, long y) {
	return x > y ? x : y;
}

long min(long x, long y) {
	return x < y ? x : y;
}

long factorial(long n) {
	if (n == 1) {
		return 1;
	}
	else {
		return n * factorial(n - 1);
	}
}

long long  fel(long long  n,long long  f) {

		if (f == 1) {
			return n % mod;
		}
		else if (f % 2 == 0) {
			return (fel(n,f / 2) * fel(n,f / 2)) % mod;
		}
		else {
			return ((n  * fel(n,f / 2) %mod) * fel(n,f / 2))% mod;
		}
	

}


int main()
{
	int n;
	cin >> n;
	double sum = 0, t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		sum = sum + 1 / t;
	}
	cout << setprecision(10)<< 1 / sum;
}



Measured memory_bytes: 256
def f(a):
	q=a[:n];s=sum(q);heapify(q);yield s
	for e in a[n:2*n]:s+=e-heappushpop(q,e);yield s
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1]))))

Measured memory_bytes: 127704