akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <queue>

using namespace std;

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

#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ff it->first
#define ss it->second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(auto i=0;i<n;++i)
#define LOOP_IT(it,s) for(auto it=(s).begin();it!=(s).end();++it)


#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

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


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


int main(int argc,char* argv[])
{
    FASTIO


    int n;
    cin>>n;
    int ar[n]={};
    vii v(n-1);
    rep(i,n-1)
    {
        cin>>v[i];
        --v[i];
        ++ar[v[i]];
    }
    rep(i,n)
    cout<<ar[i]<<"\n";


    return 0;
}



Measured memory_bytes: 4768
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

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

    using LR = tuple<int, int>;
    vector<LR> lr(m);
    vi sum(n);
    for(auto& e : lr){
        int l, r; cin >> l >> r; l--, r--;
        e = LR(l, r);
        sum[r]++;
    }
    rep(i, n-1) sum[i+1] += sum[i];

    using ABI = tuple<int, int, int>;
    vector<ABI> abi(Q);
    rep(i, Q){
        int a, b; cin >> a >> b; a--, b--;
        abi[i] = ABI(a, b, i);
    }

    sort(_all(lr));
    sort(_all(abi));

    int li = 0;
    int cnt_lout = 0;
    vi res(Q);
    for(auto& e : abi){
        int a, b, i; tie(a, b, i) = e;

        vi lazy(n);
        while(li < m){
            int l, r; tie(l, r) = lr[li];
            if(l >= a) break;
            cnt_lout++;
            lazy[r]++;
            li++;
        }
        rep(i, n-1) lazy[i+1] += lazy[i];
        rep(i, n) sum[i] -= lazy[i];

        res[i] = sum[b];
    }

    for(auto& e : res){
        cout << e << endl;
    }

    return 0;
}


Measured memory_bytes: 4096
N = int(input())
A = [int(i) for i in input().split()]

check = True
A = sorted(A)
if N % 2 == 0:
    for i in range(N):
        if i % 2 == 0 and A[i] != i + 1:
            check = False
        if i % 2 == 1 and A[i] != i:
            check = False

if N % 2 != 0:
    for i in range(N):
        if i % 2 == 0 and A[i] != i:
            check = False
        if i % 2 == 1 and A[i] != i + 1:
            check = False

if check:
    print((2 ** (N // 2)) % (10 ** 9 + 7))
else:
    print(0)


Measured memory_bytes: 13940
n = int(input())
a = []
for i in range(n):
    x,l = map(int,input().split())
    a.append([x+l,x-l])
a.sort()

ans = 1
bef = a[0]

for i in range(1,n):
    aft = a[i]
    if (bef[0] <= aft[1]):
        bef = aft
        ans += 1
print(ans)


Measured memory_bytes: 20064
n = gets.to_i
as = gets.split.map(&:to_i).sort

expected = []
if n.odd?
  if as.count == 1 && as.count(0) == 1
    puts 1
    exit
  end
  expected << 0
  ((n-1)/2).times do |i|
    expected << (i+1)*2
    expected << (i+1)*2
  end
else
  (n/2).times do |i|
    expected << i*2 + 1
    expected << i*2 + 1
  end
end

if as == expected
  puts 2 ** (n/2) % (10**9+7)
else
  puts 0
end

Measured memory_bytes: 10744
use proconio::input;
use std::cmp::max;

fn main() {
    input!{
        n: usize,
        a: [usize; n],
    }

    let mut v: Vec<(usize, usize)> = Vec::new();
    for (i, j) in a.iter().enumerate() {
        v.push((j.clone(), i));
    }
    v.sort_by(|x, y| (&y.0).cmp(&x.0));
    
    let mut d = vec![vec![0; n + 1]; n + 1];
    let f = |i: i64, j: i64| -> usize {
        ((i - j).abs()) as usize
    };
    for (i, &(act, pos)) in v.iter().enumerate() {
        for x in 0..i + 1 {
            let y = i - x;
            let m_x = f(pos as i64, x as i64);
            let m_y = f((n - y - 1) as i64, pos as i64);
            d[x + 1][y] = max(d[x + 1][y], d[x][y] + m_x * act);
            d[x][y + 1] = max(d[x][y + 1], d[x][y] + m_y * act);
        }
    }
    let ans = d.iter()
        .flat_map(|v| v).max().unwrap();
    println!("{}", ans);
}


Measured memory_bytes: 33492
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef vector<vector<P>> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<ll> vec;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
const int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30);
const int INF = (1LL << 60);
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}



signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    while(1){
        int h,w;
        cin>>h>>w;
        if(h==0&&w==0) break;
        rep(i,h){
            rep(j,w){
                if((i+j)%2==0){
                    cout<<"#";
                }
                else{
                    cout<<".";
                }
            }
            cout<<endl;
        }
        cout<<endl;
    }

}


Measured memory_bytes: 3212
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

struct UnionFind {
    int n;
    vector<int> U;
    UnionFind() {}
    UnionFind(int n_): n(n_), U(n, -1) {}
    int root(int x) {
	if (U[x] < 0) return x;
	return U[x] = root(U[x]);
    }
    int link(int x, int y) {
	x = root(x); y = root(y);
	if (x == y) return x;
	if (U[y] < U[x]) swap(x, y);
	U[x] += U[y];
	n--;
	return U[y] = x;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int size() { return n; }
    int count(int x) { return -U[root(x)]; }
};

int N, M, K;

int main() {
    scanf("%d%d", &N, &M);
    UnionFind U(N + M);
    REP (i, N) {
	scanf("%d", &K);
	REP (j, K) {
	    int x;
	    scanf("%d", &x);
	    x--;
	    U.link(i, x + N);
	}
    }

    bool yes = true;
    REP (i, N) if (!U.same(0, i)) yes = false;

    puts(yes? "YES": "NO");

    return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;

int main(void)
{
    //string a,b;
    int a,b,c,d;
    //char a,b,c;
    int i=0,sum=0;
    //char a,b='.';
    cin>>a;
    if(a>999) cout<<"ABD";
    else cout<<"ABC";
    return 0;
}



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

using namespace std;

long long a, b;

bool check(long long t)
{
    if (t < 2) return false;
    for (long long i=2; i<=(long long) sqrt(t); i++)
        if (t % i == 0) return false;
    return true;
}

void Process()
{
    long long cou = 0;

    for (long long i=1; i<=(long long) sqrt(a); i++)
        {
            long long v = i, u = a / i;
            //cout << u << " " << v << endl;
            if (a % v == 0 && b % v == 0) cou += check(v);
            if (a % u == 0 && b % u == 0 && u != v) cou += check(u);
        }

    cout << cou + 1 << endl;
}

void Input()
{
    cin >> a >> b;
}

int main()
{
    Input();
    Process();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

const double PI = 3.1415926535;

int main(){
    double r; cin >> r;
    double ans = 2.0 * PI * r;
    cout << fixed << setprecision(5) <<  ans << endl;
}

Measured memory_bytes: 3788
#include <iostream>
using namespace std;
void swap(int a[],int i,int j)
{
    int temp;
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
void pushdown(int a[],int f,int l)
{
    int p=f;
    int c=2*p;
    while (c<=l)
    {
        if(c<l&&a[c-1]>a[c])c++;
        if(a[c-1]>a[p-1])break;
        swap(a,c-1,p-1);
        p=c;
        c=2*p;
    }
}
void heap_sort(int a[],int n)
{
    int i;
    for(i=n/2;i>0;i--)pushdown(a,i,n);
    for(i=n;i>1;i--)
    {
        swap(a,0,i-1);
        pushdown(a,1,i-1);
    }
}
int main()
{
    int N,i,j;
    cin >> N;
    int A[N],B[N];
    for(i=0;i<N;i++)
    {
        cin >> A[i];
        B[i]=A[i];
    }
    heap_sort(B,N);
    for(i=0;i<N;i++)
    {
        if(A[i]==B[0])cout << B[1] << endl;
        else cout << B[0] << endl;
    }
    return 0;
}

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

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

string x = "0 1 2 3 4 5 6 7 8 9 5 4 3 2 1 ";

int main(void){
	x += x;
	int n, i, s, t, l, r;
	pair<int,string> res;
	scanf("%d", &n);
	for(;n--;){
		res.first = 12345;
		scanf("%d %d", &s, &t);
		rep(l, x.size())if(x[l] == '0' + s){
			for(r = l + 1;r < x.size();++r)if(x[r] == '0' + t)break;
			if(r < x.size() && res.first > r - l){
				res.first = r - l + 1;
				res.second = x.substr(l, r - l + 1);
			}
		}
		cout << res.second << endl;
	}
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

#define INF 0x7f7f7f
#define mem(a,b) memset(a , b , sizeof(a))
#define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll p = 1e9 + 7;
// const ll mod = 998244353;
// const int maxn = 2e5 + 10;
// const double eps = 1e - 6;

int k[100005];

void solve()
{
    string s;
    cin >> s;
    ll len = s.length();
    for(int i = 0;i < len; i++)
    {
        int l = 0, r = 0;
        if(s[i] == 'R')
        {
            while(s[i] == 'R' && i < len)
            {
                l++;
                i++;
            }
            if(l % 2 == 0)
            {
                k[i] += l / 2;
                k[i - 1] += l / 2;
            }
            else
            {
                k[i - 1] += l / 2;
                k[i] += (l - 1) / 2;
                k[i - 1]++;
            }
        }
        if(s[i] == 'L')
        {
            int t = i;
            while(s[i] == 'L' && i < len)
            {
                i++;
                r++;
            }
            if(r % 2 == 0)
            {
                k[t] += r / 2;
                k[t - 1] += r / 2;
            }
            else
            {
                k[t - 1] += r / 2;
                k[t] += (r - 1) / 2 + 1;
            }
            i--;
        }
    }
    for(int i = 0;i < len; i++)
    {
        cout << k[i] << " ";
    }
    cout << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
#ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    ios::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while(T--)
        solve();
#endif
    return 0;
}

Measured memory_bytes: 4172
#include <stdio.h>

int main()
{
	int n,a,b;
	scanf("%d",&n);
	
	if(n==1)
	{
		printf("Hello World\n");
	}
	
	if(n==2)
	{
		scanf("%d", &a);
		scanf("%d", &b);
		
		printf("%d\n",a+b);
	}
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>
#include <map>


namespace Mylib{
    using namespace std;
    
}

int main(void){
    using namespace std;
    int N;
    cin >> N;
    string tempStr;
    vector<string> vStr;
    map<string,int> MP;
    int frequent=0;
    for(int i=0;i<N;i++){
        cin >> tempStr;
        vStr.push_back(tempStr);
        MP.insert(make_pair(tempStr,0));
            
        MP[tempStr]++;
        frequent=max(frequent,MP[tempStr]);
    }
    sort(vStr.begin(),vStr.end());
    vStr.erase(unique(vStr.begin(),vStr.end()),vStr.end());
    for(auto x:vStr){
        if(MP[x]==frequent)
        cout << x << endl;
    }
    
    return 0;

}

Measured memory_bytes: 26736
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include<algorithm>
#include<sstream>
#include<iomanip>


using namespace std;


int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adj(n, vector<int>(n, 0));

	for (int i = 0; i < m;i++) {
		int a, b;
		cin >> a >>  b;
		a--;
		b--;
		adj[a][b] = 1;
		adj[b][a] = 1;
	}
	
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			if (adj[i][j] == 1) {
				long long isReach = (1LL << i);

				queue<int> q;
				q.push(i);
				while (!q.empty()) {
					int v = q.front();
					q.pop();
					for (int u = 0; u < n; u++) {

						if (adj[v][u] == 1 &&((isReach >> u) & 1) != 1 && (v!=i || u!=j)&&(u!=i && v!=j)) {
							q.push(u);
							isReach += (1LL << u);
						}
					}

				}
				if (((isReach >> j)&1) !=1) {
					cnt++;
				}

				
			}

		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
// Mo's algorithm

#include <bits/stdc++.h>

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

using namespace std;

int main(){
	int n,q; scanf("%d%d",&n,&q);
	vector<int> a(n);
	rep(i,n) scanf("%d",&a[i]), a[i]--;

	vector<int> l(q),r(q);
	rep(i,q) scanf("%d%d",&l[i],&r[i]), l[i]--;

	int m=sqrt(n);
	vector<int> p(q);
	iota(p.begin(),p.end(),0);
	sort(p.begin(),p.end(),[&](int i,int j){
		return make_pair(l[i]/m,r[i])<make_pair(l[j]/m,r[j]);
	});

	int cnt=0;
	vector<int> freq(n);
	auto add=[&](int x){
		if(freq[a[x]]==0) cnt++;
		freq[a[x]]++;
	};
	auto del=[&](int x){
		freq[a[x]]--;
		if(freq[a[x]]==0) cnt--;
	};

	vector<int> ans(q);
	int xl=0,xr=0;
	for(int i:p){
		while(xl<l[i]) del(xl++);
		while(xl>l[i]) add(--xl);
		while(xr<r[i]) add(xr++);
		while(xr>r[i]) del(--xr);
		ans[i]=cnt;
	}
	rep(i,q) printf("%d\n",ans[i]);

	return 0;
}


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

int main(void){
	int N;
	cin >> N;
	int X[N],Y[N];
	for(int i = 0; i < N;i++){
		cin >> X[i];
		Y[i] = X[i];
	}
	sort(Y,Y+N);
	/*sort(X, X+N);
	for(int i = 0; i <N/2;i++)cout << X[N/2];
	for(int i = N/2; i <N;i++)cout << X[N/2-1];*/
	for(int i = 0; i <N;i++){
		if(X[i] < Y[N/2])cout << Y[N/2]<<endl;
		else cout << Y[N/2-1] <<endl;
	}
	return 0;
}

Measured memory_bytes: 3712
f :: String->Int
f x=read x::Int
     
main = do
        e1 <- getLine
        e2 <- getLine
        e3 <- getLine
        e4 <- getLine
        let a=f e1
            b=f e2
            c=f e3
            x=f e4
        putStrLn $ show $ length $ filter (==x) [a1*500+b1*100+c1*50|a1<-[0..a],b1<-[0..b],c1<-[0..c]]

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

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

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"
#define int ll

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

  int N;
  cin>>N;
  vector<int>A(N);
  for(int i=0;i<N;i++)cin>>A[i];
  sort(rng(A));
  reverse(rng(A));
  ll ans=0;
  map<int,int>m;
  for(auto it:A)m[it]++;
  for(int i=0;i<N;i++){
    int x=log2(A[i])+1;
    int y=(1ll<<x);
    m[A[i]]--;
    if(m[y-A[i]]>0&&m[A[i]]>=0){
      m[y-A[i]]--;
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
    int n, r, max = -2000000000 , min = 2000000000;
    cin >> n;
    for ( int i = 0; i < n; i++){
        cin >> r;
        if ( r - min > max) max = r - min;
        if ( r < min) {
            min = r;
        }
    }
    
    cout << max << endl;
    
    return 0;
}


Measured memory_bytes: 3108
import java.util.Scanner;
public class Main{

    int x;

    public void input(){
	Scanner scan = new Scanner(System.in);
       x = scan.nextInt();
        
    }
 


    public void output(){
	System.out.println(x*x*x);
    }
 public static void main(String[] args){
     Main p = new Main();
     p.input();
     p.output();
 }
}
  

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

int main()
{
	int r, c, a[101][101] = { };
	cin >> r >> c;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> a[i][j];
			a[i][c] += a[i][j];
			a[r][j] += a[i][j];
			a[r][c] += a[i][j];
		}
	}
	for (int i = 0; i <= r; i++)
	{
		for (int j = 0; j <= c; j++)
		{
			cout << a[i][j];
			if (j != c)
			{
				cout << " ";
			}
			else
			{
				cout << endl;
			}
		}
	}
}


Measured memory_bytes: 3156
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
struct dice{
  int up,s,e,w,n,dn;
  void to(char dir){
    if(dir=='N'){
      int tmp = n;
      n = up;
      up = s;
      s = dn;
      dn = tmp;
    }else if(dir=='S'){
      int tmp = s;
      s = up;
      up = n;
      n = dn;
      dn = tmp;
    }else if(dir=='E'){
      int tmp = e;
      e = up;
      up = w;
      w = dn;
      dn = tmp;
    }else if(dir=='W'){
      int tmp = w;
      w = up;
      up = e;
      e = dn;
      dn = tmp;
    }
  }
  void to(string dirs){
    REP(i,dirs.size()) to(dirs[i]);
  }
};
signed main(){
  int a[6];
  REP(i,6) cin >> a[i];
  dice di = {a[0],a[1],a[2],a[3],a[4],a[5]};
  string s;
  cin >> s;
  di.to(s);
  cout << di.up << endl;
}



Measured memory_bytes: 3192
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>

typedef long long ll;
int N,a,b,ans;
int main(){
    scanf("%d",&N);
    a=(N/15)*200;
    b=N*800;
    ans=b-a;
    printf("%d",ans );
    return 0;
}


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

using ll = long long;

constexpr ll MOD = 1e9+7;
constexpr ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

int main(int argc, char **argv)
{
	string s; cin >> s;
	stack<char> st;

	ll tmp{0};
	for (auto &e : s)
	{
		if (st.empty()) st.push(e);
		else if (st.top() == 'S' && e == 'T') {++tmp; st.pop();}
		else {st.push(e);}
	}
	std::cout << s.size() - 2*tmp << std::endl;
}

Measured memory_bytes: 644
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll n,k;cin >> n >>k;
    vl v(50,0);
    rep(i,n){
        ll a;cin >> a;
        rep(j,50){
            if(a&((ll)1<<j))v[j]++;
        }
    }
    vl s(50,0);
    rep(i,50)if(k&((ll)1<<i))s[i]=1;
    rev(all(v));rev(all(s));
    ll dp0[51];
    ll dp1[51];
    rep(i,51){dp0[i]=0;dp1[i]=0;}
    rep(i,50){
        if(dp0[i]>0)chmax(dp0[i+1],dp0[i]+(n-v[i])*((ll)1<<(49-i)));
        if(dp0[i]>0)chmax(dp0[i+1],dp0[i]+v[i]*((ll)1<<(49-i)));
        if(s[i]==0){
            chmax(dp1[i+1],dp1[i]+v[i]*((ll)1<<(49-i)));
        }
        else {
            chmax(dp1[i+1],dp1[i]+(n-v[i])*((ll)1<<(49-i)));
            chmax(dp0[i+1],dp1[i]+v[i]*((ll)1<<(49-i)));
        }
    }
    cout << max(dp0[50],dp1[50]) <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric> // accumulate
#include <queue>
#include <string>
#include <cmath> // sqrt
#include <map>
using namespace std;
typedef long long ll;

const int INF = 1000000010;
ll dp[110][100010];

int main() {
    int N, W;
    cin >> N >> W;

    for (int i = 0; i < N; i++) {
        int w, v;
        cin >> w >> v;

        for (int weight = 0; weight <= W; weight ++) {
            if (weight - w >= 0) dp[i+1][weight] = max(dp[i][weight], dp[i][weight-w] + v);
            else dp[i+1][weight] = dp[i][weight];
        }
    }

    ll ans = 0;
    for (int weight = 0; weight <= W; weight++) {
        ans = max(ans, dp[N][weight]);
    }

    cout << ans << endl;
}

Measured memory_bytes: 79360
#include<bits/stdc++.h>
using namespace std;
int dp[200005];
int a[200005];
int main()
{
    int n,k;
    cin>>n>>k;

    for(int i=1; i<=n; i++) cin>>a[i];
    dp[2]=abs(a[2]-a[1]);
    for(int i=3; i<=n; i++) dp[i]=INT_MAX;
    for(int i=3; i<=n; i++)
    {
        for(int j=max(1,i-k); j<i; j++)
        {
            dp[i]=min(dp[i],(dp[j]+abs(a[i]-a[j])));
        }

    }
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include<vector>
#include<iostream>
#include<string>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<cmath>
#include<algorithm>
#include<numeric>
#define LONG long long int
using namespace std;

int main() {
	long long int r, D, x;
	cin >> r >> D >> x;

	for (int i = 0; i < 10; i++)
	{
		x = r * x - D;
		cout << x << endl;
	}


	return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

#ifdef DEBUG
#else
    #define cerr if (false) cerr
#endif

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    string s;
    cin >> s;
    int r = 0;
    for (char c : s)
        r = (r + c - '0') % 9;
    cout << (r == 0 ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 3764
from heapq import heappush, heappop

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


def get_area():
    mp = ["#" * (w + 2)]
    for _ in range(h):
        mp.append("#" + input() + "#")
    mp.append("#" * (w + 2))
    return mp


areas = [get_area()]
times = {}
n = int(input())
for i in range(n):
    times[int(input())] = i + 1
    areas.append(get_area())

for y in range(1, h + 1):
    for x in range(1, w + 1):
        if areas[0][y][x] == "S":
            sx, sy = x, y
        if areas[0][y][x] == "G":
            gx, gy = x, y

que = []
heappush(que, (0, 0, sx, sy, 0))
dic = {}
dic[(0, sx, sy)] = 0
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
checked = [[False] * (w + 2) for _ in range(h + 2)]
while que:
    score, time, x, y, area_num = heappop(que)
    if (x, y) == (gx, gy):
        print(score)
        break
    time += 1
    if time in times:
        area_num += 1

    area = areas[area_num]
    for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if area[ny][nx] == "#" :continue
        if (time, nx, ny) not in dic:
            if area_num != n:
                dic[(time, nx, ny)] = score + 1
                heappush(que, (score + 1, time, nx, ny, area_num))
            elif not checked[ny][nx]:
                dic[(time, nx, ny)] = score + 1
                checked[ny][nx] = True
                heappush(que, (score + 1, time, nx, ny, area_num))
    if area[y][x] != "#" and not checked[y][x] and ((time, x, y) not in dic or dic[(time, x, y)] > score):
        dic[(time, x, y)] = score
        heappush(que, (score, time, x, y, area_num))
        if area_num == n:checked[y][x] = True
else:
    print(-1)




Measured memory_bytes: 9180
N, M = map(int, input().split())

A = []
B = []
for _ in range(N):
    A.append(input())
for _ in range(M):
    B.append(input())

def CheckExist(ai, aj):
    for bi in range(M):
        for bj in range(M):
            if A[ai+bi][aj+bj] != B[bi][bj]:
                return False
    return True

for ai in range(N - M + 1):
    for aj in range(N - M + 1):
        if CheckExist(ai, aj):
            print('Yes')
            exit(0)
print('No')

Measured memory_bytes: 3064
// Sakhiya07 - Yagnik Sakhiya
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define mp make_pair
#define bp __builtin_popcountll
#define MOD  998244353
const int N = 200005;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

void solve()
{
    ll n;
    cin >> n;
    cout<<endl;
    ll val;
    val = 0;
    string last;
    cout<<"0"<<endl;
    cout<<endl;
    cin>>last;
    if(last=="Vacant")   return;
    ll low = 1,high = n-1;
    while(low<=high)
    {
        ll mid = (low + high)/2;
        cout<<mid;
        cout<<endl;
        string now;
        cin >> now;
        cout<<endl;
        if(now=="Vacant")   return;
        ll chk = 0;
        if((mid-val)%2)
        {
            if(now==last) 
            {
                chk = 1;
            }
        }
        else 
        {
            if(now!=last)
            {
                chk = 1;
            }
        }
        if(chk)     high = mid - 1;
        else
        {
            low = mid + 1;
            val = mid;
            last = now;
        }
    }
}


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

Measured memory_bytes: 1224
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

/* 一つ読み */
func scanText() string {
	sc.Scan()
	return sc.Text()
}
func scanInt() int {
	sc.Scan()
	a, err := strconv.Atoi(sc.Text())
	if err != nil {
		fmt.Println(err)
	}
	return a
}
func scanFloat() float64 {
	sc.Scan()
	a, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		fmt.Println(err)
	}
	return a
}

/* 複数読み */
func scanTextSlice(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = scanText()
	}
	return a
}
func scanSlice(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = scanInt()
	}
	return a
}
func scanFloatSlice(n int) []float64 {
	a := make([]float64, n)
	for i := 0; i < n; i++ {
		a[i] = scanFloat()
	}
	return a
}

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	a := scanInt()
	b := scanInt()
	c := scanInt()
	x := scanInt()

	count := 0

	for ia := 0; ia <= a; ia++ {
		for ib := 0; ib <= b; ib++ {
			for ic := 0; ic <= c; ic++ {
				if ia*500+ib*100+ic*50 == x {
					count++
				}
			}
		}
	}

	fmt.Println(count)
}

Measured memory_bytes: 1772
from sys import stdin, exit

N = int(stdin.readline().rstrip())
work = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]

work.sort(key=lambda x: x[1])
time = 0
for k in range(N):
    if time + work[k][0] > work[k][1]:
        print('No')
        exit()
    time += work[k][0]
print('Yes')


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

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll p,i,k;
	cin >> k;
	p = 0;
	for(i=1;i<=1e7;++i)
	{
		p = ((p*10)%k+7)%k;
		if(p == 0)
		{
			cout << i << "\n";
			return 0;
		}
	}
	cout << -1 << "\n";
}

Measured memory_bytes: 3652
#include<stdio.h>

int main(void){
    int n,h[100000];
    int max=0;
    int count=0;
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&h[i]);
    }
    for (int i = 0; i < n; i++)
    {
        count=0;
        int j;
        for (j = i; j < n-1; j++)
        {
            if(h[j]>=h[j+1])
            {
                count++;
            }else
            {
                break;
            }
        }
        printf("\n");
        if (max<=count)
        {
            max=count;
        }
        i=j;

    }
    printf("%d\n",max);
    return 0;
}

Measured memory_bytes: 640
int G(x,y){return y?G(y,x%y):x;}
long long L(long long x,long long y){return x/G(x,y)*y;}
n[3],a[3],m[3];main(i,x){
	for(;scanf("%d%d%d%d%d%d",a,m,a+1,m+1,a+2,m+2),*m;){
		for(i=3;i--;)for(x=n[i]=1;(x=a[i]*x%m[i])>1;n[i]++);
		printf("%lld\n",L(n[0],L(n[1],n[2])));
	}
}

Measured memory_bytes: 600
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 10000000;
const long long inf = 1ll<<61;
typedef pair<int, int> P;
typedef pair<P, int> PP;
typedef pair<int,PP> PPP;
struct edge { int to;  int cost; };
vector<edge>G[114514];
int dis[100005];
int num[100005];
int n, m; 
int x[100005], y[100005], S[100005];
void bfs() {
	fill(dis, dis + n, inf);
	dis[0] = 0;
	queue<P>Q;
	Q.push(P(0, 0));
	while (Q.size()) {
		P p = Q.front(); Q.pop();
		int v = p.second;
		if (dis[v] < p.first)continue;
		rep(i, G[v].size()) {
			edge e = G[v][i];
			if (dis[e.to] > dis[v] + 1) {
				dis[e.to] = dis[v] + 1;
				Q.push(P(dis[e.to], e.to));
			}
		}
	}

}

void dfs(int x) {
	rep(i, G[x].size()) {
		int now = G[x][i].to;
		if (dis[x] != dis[now]&&num[G[x][i].to]==inf) {
			num[now] = G[x][i].cost - num[x];
			dfs(G[x][i].to);
		}
	}
}

signed main() {
	cin >> n >> m;
	rep(i, m) {
		int u, v, s; cin >> u >> v >> s;
		u--; v--;
		G[u].push_back({v,s});
		G[v].push_back({ u,s });
		x[i] = u; y[i] = v; S[i] = s;
	}
	fill(num, num + n, inf);
	num[0] = 1;
	bfs();
	dfs(0);

	int om = inf, em = inf;
	rep(i, n) {
		if (dis[i] & 1)om = min(om, num[i]);
		else em = min(em, num[i]);
	}
	
	set<int>st;
	rep(i, m) {
		if (dis[x[i]] == dis[y[i]]) {
			if (dis[x[i]] & 1) {
				int dif = num[x[i]] + num[y[i]] - S[i];
				if (abs(dif) & 1) {
					puts("0");
					return 0;
				}
				dif /= 2;
				st.insert(dif);
			}
			else{
			int dif = S[i] - num[x[i]] - num[y[i]];
			if (abs(dif) & 1) {
				puts("0");
				return 0;
			}
			dif /= 2;
			st.insert(dif);
			}
		
		}
		else {
			if (num[x[i]] + num[y[i]] != S[i]) {
				puts("0");
				return 0;
			}
		}
	}
	if (st.size() > 1)puts("0");
	else if(st.size()==1){
		auto itr = st.begin();
		int x = *itr;
		rep(i, n) {
			if (dis[i] & 1)num[i] -= x;
			else num[i] += x;
		}
		int flg = 0;
		rep(i, n) { if (num[i] <= 0)flg++; 
		}
		if (flg)puts("0");
		else puts("1");
	}
	else {
		cout << max((om + em) -1,0ll) << endl;
	}
}

Measured memory_bytes: 16768
# include<iostream>
# include<cmath>
# include<math.h>
struct Point{
  double x;
  double y;
};

Point calc_st(Point a, Point b){
  Point c;
  c.x = (2*a.x + b.x) / 3;
  c.y = (2*a.y + b.y) / 3;
  return c;
}
Point calc_u(Point a, Point b){
  Point c;
  c.x = (b.x - a.x)*cos(M_PI/3) - (b.y - a.y)*sin(M_PI/3) + a.x;
  c.y = (b.x - a.x)*sin(M_PI/3) + (b.y - a.y)*cos(M_PI/3) + a.y;
  return c;
}

void koch(int n, Point p1, Point p2){
  Point s,t,u;
  if(n == 0) return;
  //p1 p2 から凸(s,t,u)を求める。
    s = calc_st(p1, p2);
    t = calc_st(p2, p1);
    u = calc_u(s, t);
  koch(n-1, p1, s);
  printf("%lf %lf\n", s.x, s.y);
  koch(n-1, s, u);
  printf("%lf %lf\n", u.x, u.y);
  koch(n-1, u, t);
  printf("%lf %lf\n", t.x, t.y);
  koch(n-1, t, p2);
  return;
}
int main(){
  int n; scanf("%d",&n);
  Point p1 = {0,0}, p2 ={100,0};
  printf("%lf %lf\n", p1.x, p1.y);
  koch(n, p1, p2);
  printf("%lf %lf\n", p2.x, p2.y);
  return 0;
}


Measured memory_bytes: 3176
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>

using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9

int main() {
	int a, b;
	cin >> a >> b;
	cout << max({ a + b,a - b,a*b }) << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

class Pair implements Comparable<Pair> {

    final int index;
    final int count;

    Pair( int index, int count ) {
	this.index = index;
	this.count = count;
    }

    public int compareTo( final Pair pair ) {
	if ( count != pair.count ) {
	    return pair.count - count;
	} else {
	    return index - pair.index;
	}
    }    
}

class Main {

    public static void main( final String[] args ) {

	final Scanner stdin = new Scanner( System.in );

	while ( true ) {

	    final int n = stdin.nextInt();
	    final int m = stdin.nextInt();

	    if ( n == 0 && m == 0 ) {
		break;
	    }

	    int[] count = new int[ m ];
	    for ( int i = 0; i < n; i++ ) {
		for ( int j = 0; j < m; j++ ) {
		    if ( stdin.nextInt() == 1 ) {
			count[ j ]++;
		    }
		}
	    }

	    ArrayList<Pair> pairList = new ArrayList<Pair>();
	    for ( int i = 0; i < m; i++ ) {
		pairList.add( new Pair( i, count[ i ] ) );
	    }
	    Collections.sort( pairList );
	    for ( int i = 0; i < m; i++ ){
		if ( i > 0 ) {
		    System.out.print( " " );
		}
		System.out.print( pairList.get( i ).index + 1 );
	    }
	    System.out.println();
	}	
    }    
}

Measured memory_bytes: 64132
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<random>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
typedef vector<vt>vvt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
#define yes cout<<"Yes\n"
#define no cout<<"No\n"


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

	int n;
	cin>>n;
	vi a(n),b(n);
	rep(i,n)cin>>a[i]>>b[i];
	sort(all(a));
	sort(all(b));
	if(n%2){
		cout<<b[n/2]-a[n/2]+1<<endl;
	}else{
		cout<<b[n/2]+b[n/2-1]-a[n/2]-a[n/2-1]+1<<endl;
	}
}


Measured memory_bytes: 6332
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
using ll=long long int;

constexpr int INF = 1e9+7;

int main() {
    int n;
    cin >> n;
    vector<int> w(n);
    for (auto &e: w) cin >> e;

    int ans = INF;
    for (int i = 1; i < n; ++i) {
        int s1 = accumulate(w.begin(), w.begin()+i, 0);
        int s2 = accumulate(w.begin()+i, w.end(), 0);
        ans = min(ans, abs(s1-s2));
    }

    cout << ans << endl;

    return 0;
}


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

int main(){
  long double a,b,c;
  cin >>a>>b>>c;
  
  if(c-a-b<=0){
    cout<<"No"<<endl;
    return 0;
  }
    
  if(4*a*b<pow((c-a-b),2)){
    cout<<"Yes"<<endl;
    return 0;
  }

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

  
  
  

  

Measured memory_bytes: 256
W,H,N = map(int,input().split())
Xu,Xd,Yu,Yd=W,0,H,0
for i in range(N):
  x,y,a = map(int,input().split())
  if a==1:
    Xd=max(Xd,x)
  elif a==2:
    Xu=min(Xu,x)
  elif a==3:
    Yd=max(Yd,y)
  elif a==4:
    Yu=min(Yu,y)
X = max(0,Xu-Xd)
Y = max(0,Yu-Yd)
print(X*Y)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
pair<int,int> tr[100001];
int tm[100001];
int id[100001];
 
int main(){
  int n,r,l;
  cin>>n>>r>>l;
  for(int i=1;i<=n;i++){
    tr[i]=make_pair(0,i);
    id[i]=i;
  }
  int rt=0;
  for(int k=0;k<r;k++){
    int d,t,x;
    cin>>d>>t>>x;
    tm[tr[1].second]+=t-rt;
    rt=t;
    tr[id[d]].first-=x;
    int u=id[d];
    pair<int,int> tem;
    if(x>0){
      while(u!=1&&tr[u]<tr[u/2]){
    tem=tr[u];
    tr[u]=tr[u/2];
    tr[u/2]=tem;
    id[tr[u].second]=u;
    id[tr[u/2].second]=u/2;
    u/=2;
      }
    }
    else {
      while(2*u+1<=n&&(tr[u]>tr[2*u]||tr[u]>tr[2*u+1])){
    int du=(tr[2*u]<tr[2*u+1])?(2*u):(2*u+1);
    tem=tr[u];
    tr[u]=tr[du];
    tr[du]=tem;
    id[tr[u].second]=u;
    id[tr[du].second]=du;
    u=du;
      }
    }
  }
  tm[tr[1].second]+=l-rt;
  int maxtm=0,tmid;
  for(int i=1;i<=n;i++){
    if(maxtm<tm[i]){
      tmid=i;
      maxtm=tm[i];
    }
  }
  cout<<tmid<<endl;
   
  return 0;
}

Measured memory_bytes: 2720
h,w = map(int,input().split())
#0が進めるところ、1は無理
#lis = [[1 if l == '#' else 0 for l in list(input())] for _ in range(h)]

road_count = 0
lis = [list('#'*(w+2))]
for _ in range(h):
    li = input()
    for i in li:
        if i == '.':
            road_count += 1
    li = '#' + li + '#'
    lis.append(list(li))
lis.append(list('#'*(w+2)))

#print(lis)
dp = [[0]*(w+2) for _ in range(h+2)]

#(開始x,開始y,移動回数)
step = [[1,1]]
while len(step)>0:
    x,y = step.pop(0)

    if x == h and y == w:
        print(road_count-dp[x][y]-1)
        exit()

    #探索済みのところは、#にする
    lis[x][y] = '#'


    if lis[x-1][y] != '#' and dp[x-1][y] == 0:
        step.append([x-1,y])
        dp[x-1][y] = dp[x][y]+1
    if lis[x+1][y] != '#' and dp[x+1][y] == 0:
        step.append([x+1,y])
        dp[x+1][y] = dp[x][y]+1
    if lis[x][y-1] != '#' and dp[x][y-1] == 0:
        step.append([x,y-1])
        dp[x][y-1] = dp[x][y]+1
    if lis[x][y+1] != '#' and dp[x][y+1] == 0:
        step.append([x,y+1])
        dp[x][y+1] = dp[x][y]+1
print(-1)

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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define foreach(e, v) for (auto &e : v)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = __INT_MAX__;               // 2^31 - 1
const long long INFLL = __LONG_LONG_MAX__; // 2^61 - 1
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

struct mint {
    // Preparation: MOD is already defined.
    ll value;

    mint(ll value = 0) : value((value % MOD + MOD) % MOD) {}

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    mint pow(mint m) const {
        return pow(m.value);
    }

    mint inv() const {
        ll a = value, b = MOD, u = 1, v = 0;
        while (b) {
            ll t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        u %= MOD;
        return u;
    }

    mint &operator+=(const mint a) {
        if ((value += a.value) >= MOD) value -= MOD;
        return *this;
    }
    mint &operator-=(const mint a) {
        if ((value += MOD - a.value) >= MOD) value -= MOD;
        return *this;
    }
    mint &operator*=(const mint a) {
        (value *= a.value) %= MOD;
        return *this;
    }
    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

int main() {
    set<int> available = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n, m;
    cin >> n >> m;
    rep(i, m) {
        int d;
        cin >> d;
        available.erase(d);
    }

    auto cond = [&](int x) {
        if (available.find(x) != available.end())
            return true;
        else
            return false;
    };
    repeat(i, n, 10 * n) {
        int d = i;
        bool ok = true;
        while (d > 0) {
            int x = d % 10;
            if (!cond(x))
                ok = false;
            d /= 10;
        }
        if (ok) {
            out(i);
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  string s;cin>>s;

  string ans="";
  for(int t=0;t<s.size();t++){
    if(s[t]=='B'){
      if(ans.size()==0)continue;
      ans=ans.substr(0,ans.size()-1);
    }else{
      ans+=s[t];
    }
  }

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


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

int main(){
  
  long long X, N, T, time;
  cin>>N>>X>>T;
  
  if(N%X!=0){
    time=((long long)N/X+1)*T;
  }else{
    time=((long long)N/X)*T;
  }
  cout<<time<<endl;
  return 0;
}

Measured memory_bytes: 3600