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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,A,B;
const ll mo=1000000007;

ll dp[5050][5050][2];
ll add[15050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	if(A>B) swap(A,B);
	
	dp[0][0][0]=1;
	FOR(i,N) {
		if(i) {
			(add[i]+=add[i-1])%=mo;
			(dp[i][1][0]+=add[i])%=mo;
		}
		FOR(j,N+1) {
			if(j>=B) {
				(dp[i+1][B][0]+=dp[i][j][0]*2)%=mo;
				(dp[i+1][B][0]+=dp[i][j][1]*2)%=mo;
			}
			else {
				(dp[i+1][j+1][0]+=dp[i][j][1])%=mo;
				(dp[i+1][j+1][1]+=dp[i][j][1])%=mo;
				// B
				(dp[i+1][j+1][0]+=dp[i][j][0])%=mo;
				// A
				if(dp[i][j][0]) {
					(add[i+2]+=dp[i][j][0])%=mo;
					(add[i+A+1]+=mo-dp[i][j][0])%=mo;
					/*
					for(x=1;i+x+1<=N&&x<A;x++) if(dp[i][j][0]) {
						(dp[i+x+1][1][0]+=dp[i][j][0])%=mo;
					}
					*/
					if(i+A<=N) (dp[i+A][min(B,j+A)][1]+=dp[i][j][0])%=mo;
				}
			}
		}
	}
	
	cout<<(dp[N][B][0]+dp[N][B][1])%mo<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 398188
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<iostream>
#include<string>
using namespace std;

int main(){
	map<string,int>songs;
	string str;
	int n,time[60];
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>str;
		scanf("%d",&time[i]);
		songs[str]=i;
	}
	
	cin>>str;
	int sum=0;
	for(int i=songs[str]+1;i<=n;i++){
		sum+=time[i];
	}
	
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from operator import itemgetter
 
N,M = map(int,readline().split())
m = map(int,read().split())
AB = sorted(zip(m,m))
AB.sort(key = lambda x: x[1])


c = AB[0][1]
ans = 1
for i in range(1,M):
	if AB[i][0] < c:
		continue
	else:
		ans += 1
		c = AB[i][1]

print(ans)

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

#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)

int main(){
  string s;
  int k;
  cin >> s >> k;
  int n = s.size();
  vector<string> v;
  string sub;
  rep(i,n){
    rep(j,min(n-i,5)){
      sub = s.substr(i,j+1);
      v.push_back(sub);
    }
  }
  sort(all(v));
  unique(all(v));
  cout << v[k-1] << endl;
}

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

int main(){
  int N,M;
  cin >> N >> M;
  vector<vector<int>> S(M);
  for(int i=0;i<M;i++){
    int k;
    cin >> k;
    for(int j=0;j<k;j++){
      int a;
      cin >> a;
      a --;
      S[i].push_back(a);
    }
  }
  vector<int> P(M);
  for(int i=0;i<M;i++) cin >> P[i];
  int ans=0;
  for(int bit=0;bit < (1<<N); ++bit){
    bool ok = true;
    for(int i=0;i<M;i++){
      int sum = 0;
      for(int j=0;j<S[i].size();j++){
        if(bit&(1<<S[i][j])){
          sum ++;
        }
      }
      if(sum%2!=P[i]){
        ok=false;
        break;
      }
    }
    if(ok){
      ans ++;
    }
  }
  cout << ans << endl;
}

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

int main() {
	char c;
	cin >> c;

	if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
		cout << "vowel\n";
	}
	else {
		cout << "consonant\n";
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

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

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

void dfs(vector<ll> &ki,vector<vector<ll>> &z,ll now, vector<ll> &ans, vector<ll> &seen) {
    seen[now] = 1;
    for (int i = 0; i < z[now].size(); i++) {
        if (seen[z[now][i]] == 0) {
            dfs(ki, z, z[now][i], ans, seen);
            ki[now] += ki[z[now][i]];
            ans[now] = max(ans[now], ki[z[now][i]]);
        }
    }
    ki[now]++;
    ll p = ki.size();
    if (now != 0)ans[now] = max(ans[now],p - ki[now]);
    return;
}

int main() {
    ll n, c;
    cin >> n >> c;
    vector<vector<ll>> z(c,vector<ll>(100001));
    for (int i = 0; i < n; i++) {
        ll a, b, d;
        cin >> a >> b >> d;
        for (int j = a - 1; j < b; j++) {
            z[d - 1][j] = 1;
        }
    }
    ll ans = 0;
    for (int i = 0; i < 100001; i++) {
        ll zans = 0;
        for (int j = 0; j < c; j++) {
            zans += z[j][i];
        }
        ans = max(ans, zans);
    }
    cout << ans << endl;
}

Measured memory_bytes: 24952
#include<cstdio>
const int maxn = 1e5+10;

int a,b,m,as[maxn],bs[maxn],a1,b1,c1;
int main()
{
  int min1 = 0x3f3f3f3f,min2 = 0x3f3f3f3f;
  scanf("%d%d%d",&a,&b,&m);
  for(int i=1;i<=a;i++){scanf("%d",&as[i]);if(min1>=as[i])min1 = as[i];}
  for(int i=1;i<=b;i++){scanf("%d",&bs[i]);if(min2>=bs[i])min2 = bs[i];}
  int ans = min1+min2;

  for(int i=1;i<=m;i++)
  {
    scanf("%d%d%d",&a1,&b1,&c1);
    if(as[a1]+bs[b1]-c1 < ans)ans = as[a1]+bs[b1]-c1;
  }
  printf("%d", ans);
  return 0;
}


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

typedef long long ll;

using namespace std;


ll mod = pow(10, 9) + 7;

ll re(ll n, ll sq){
    if(sq == 0) return 1;
    if(sq % 2 == 0){
        ll t = re(n, sq / 2);
        return t * t % mod;
    } else {
        ll t = re(n, sq - 1);
        return n * t % mod;
    }
}


int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    ll bc = 1;
    ll bb = 1;
    for(int i = 0; i < a; i++){
        bc = (bc * (n - i)) % mod;
        bb = (bb * (i + 1)) % mod;
    }
    ll bbg = re(bb, mod - 2);
    ll ad = (bc % mod) * (bbg % mod) % mod;

    bc = 1;
    bb = 1;
    for(int i = 0; i < b; i++){
        bc = (bc * (n - i)) % mod;
        bb = (bb * (i + 1)) % mod;
    }

    bbg = re(bb, mod - 2);
    ll bd = (bc % mod) * (bbg % mod) % mod;

    ll ans = (re(2, n) - 1);
    ans = ((ans - ad) % mod - bd) % mod;

    if(ans < 0){
        cout << mod + ans << endl;
    } else {
        cout << ans << endl;
    }
}

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

long long gcd(long long a, long long b){
    if (b == 0) return a;
    else return (gcd(b, a % b));
}

void solve(long long A, long long B){
    cout << (A * B) / gcd(A,B) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


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

int main(){
  int s, x, y, z;
  cin >> s;
  
  x = s / 100;
  y = s/10 - x*10;
  z = s - x*100 - y*10;
  
  cout << x+y+z << endl;
}
  

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

int main() {
    string s;
    cin>>s;
    int z=0,o=0;
    for (auto c:s) {
        if (c=='0')
            z++;
        else o++;
    }
    cout<<min(z,o)*2<<endl;
    return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
int main(){
	int card[4][13]={0},ch,num,N;
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf(" %c %d",&ch,&num);
		if(ch == 'S'){
			card[0][num-1]=1;
		}
		else if(ch == 'H'){
			card[1][num-1]=1;
		}
		else if(ch == 'C'){
			card[2][num-1]=1;
		}
		else{
			card[3][num-1]=1;
		}
	}
	for(int x=0;x<4;x++){
		for(int y=0;y<13;y++){
			if(x==0){
				if(card[0][y]==0) printf("S %d\n",y+1);
			}
			else if(x==1){
				if(card[1][y]==0) printf("H %d\n",y+1);
			}
			else if(x==2){
				if(card[2][y]==0) printf("C %d\n",y+1);
			}
			else{
				if(card[3][y]==0) printf("D %d\n",y+1);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2720
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<int(n); i++)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

int N;
ll c[200010],ans[200010];
vector<int> G[200010];

void solve(int now, int num){
	c[now] = num;
	for(int i=0; i<G[now].size(); i++){
		if(c[G[now][i]] == 0){
			solve(G[now][i], 3-num);
		}
	}
	return;
}

int main(){
	int N; cin >> N;
	rep(i, N-1){
		int a, b; cin >> a >> b; a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	solve(0, 1);
	int one = 0, two = 0;
	rep(i, N){
		if(c[i] == 1) one++;
		else two++;
	}
	int p, q;
	if(N % 3 == 0){
		int k = N/3;
		if(one >= k){
			p = 1;
			one -= k;
			if(one >= k){
				q = 1;
			}else{
				q = 2;
			}
		}else{
			p = 2, q = 2;
		}
	}else if(N % 3 == 1){
		int k = N/3;
		if(one >= k+1){
			p = 1;
			one -= (k+1);
			if(one >= k){
				q = 1;
			}else{
				q = 2;
			}
		}else{
			p = 2, q = 2;
		}
	}else{
		int k = N/3;
		if(one >= k+1){
			p = 1;
			one -= (k+1);
			if(one >= k+1){
				q = 1;
			}else{
				q = 2;
			}
		}else{
			p = 2, q = 2;
		}
	}
	if(p==1){
		int x = 1;
		rep(i, N){
			if(x > N) break;
			if(c[i] == 1){ ans[i] = x; x += 3; }
		}
	}else{
		int x = 1;
		rep(i, N){
			if(x > N) break;
			if(c[i] == 2){ ans[i] = x; x += 3; }
		}
	}
	if(q==1){
		int x = 2;
		rep(i, N){
			if(x > N) break;
			if(c[i] == 1 && ans[i] == 0){ ans[i] = x; x += 3; }
		}
	}else{
		int x = 2;
		rep(i, N){
			if(x > N) break;
			if(c[i] == 2 && ans[i] == 0){ ans[i] = x; x += 3; }
		}
	}
	int x = 3;
	rep(i, N){
		if(ans[i] == 0){
			ans[i] = x;
			x += 3;
		}
		cout << ans[i] << " ";
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 20480
n = int(input())

all = int((n+1)*(n/2))
fizz = int(3*((n//3 + 1)*((n//3)/2)))
buzz = int(5*((n//5 + 1)*((n//5)/2)))
fizzbuzz = int(15*((n//15 + 1)*((n//15)/2)))

result =  all - fizz - buzz + fizzbuzz
print(result)

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

int findSumOfDigits(int n){
    int sum=0;
    while (n>0) {
        sum += n%10;
        n /= 10;
    }return sum;
}

int main(){
    int N,A,B;
    cin>>N>>A>>B;
    int total=0;
    for (int i=1; i<=N; i++) {
        int sum = findSumOfDigits(i);
        if (sum >=A && sum<=B) {
            total += i;
        }
    }
    cout<<total<<endl;
    return 0;
}

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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;

    if (a == b)
    {
        cout << c << endl;
    }
    else if (a == c)
    {
        cout << b << endl;
    }
    else
    {
        cout << a << endl;
    }
}

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

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using uint=unsigned int;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

ll readLL(){
	ll i;
	scanf("%lld",&i);
	return i;
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

const int mod=1000000007;
template<class T,class U>
void add(T& a,U b){
	a=((ll)a+b)%mod;
}

template<>
void add(int& a,int b){
	a+=b;
	if(a>=mod)a-=mod;
}

template<class T,class U>
void sub(T& a,U b){
	a=((ll)a-b%mod+mod)%mod;
}

template<>
void sub(int& a,int b){
	a-=b;
	if(a<0)a+=mod;
}

template<class T,class U>
void mult(T& a,U b){
	a=((ll)a*b)%mod;
}

ll modPow(ll a,ll p){
	ll s=1;
	REP(i,30){
		if((p>>i)&1)
			mult(s,a);
		mult(a,a);
	}
	return s;
}

ll modInv(ll a){
	return modPow(a,mod-2);
}

struct UnionFind{
	vi rank,par;
	void Init(int n){
		rank.assign(n,0);
		par.assign(n,-1);
	}
	int Find(int i){
		return par[i]==-1?i:(par[i]=Find(par[i]));
	}
	bool Same(int a,int b){
		return Find(a)==Find(b);
	}
	bool Unite(int a,int b){
		a=Find(a);
		b=Find(b);
		if(a==b)
			return false;
		if(rank[a]<rank[b])
			swap(a,b);
		par[b]=a;
		if(rank[a]==rank[b])
			rank[a]++;
		return true;
	}
} uf;

int main(){
	int h=read(),w=read();
	vector<string> buf;
	REP(i,h)
		buf.PB(readString());
	int ans=1;
	if(h>=2&&w>=2){
		int oed=0;
		uf.Init(h/2+w/2);
		REP(i,h/2)REP(j,w/2){
			int tmp[4];
			int used[26]={};
			tmp[0]=buf[i][j]-'a';
			tmp[1]=buf[i][w-1-j]-'a';
			tmp[2]=buf[h-1-i][j]-'a';
			tmp[3]=buf[h-1-i][w-1-j]-'a';
			int way=24;
			REP(k,4)
				way/=(++used[tmp[k]]);
			if(way==24){
				oed++;
				if(!uf.Same(i,h/2+j))
					mult(ans,2);
				uf.Unite(i,h/2+j);
				mult(ans,12);
			}else
				mult(ans,way);
		}
	}
	if(h%2==1){
		string s=buf[h/2];
		string t=s;reverse(t.begin(),t.end());
		if(s!=t)
			mult(ans,2);
	}
	if(w%2==1){
		string s;
		REP(i,h)
			s+=buf[i][w/2];
		string t=s;reverse(t.begin(),t.end());
		if(s!=t)
			mult(ans,2);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 2304
from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    X = []
    for _ in range(N):
        a,b = map(int,input().split())
        X.append((b,a))

    x = 0
    X.sort(key=lambda x: x[0])
    X = deque(X)
    l = len(X)
    for _ in range(l):
        b,a = X.popleft()
        # print(b,a,x)
        if x + a > b:
            print("No")
            exit()

        x += a

    print("Yes")



if __name__ == "__main__":
  main()

Measured memory_bytes: 32224
from collections import deque

N = int(input())

gr = { i:[] for i in range(N+1)}

for i in range(N-1):
  a,b,c = map(int,input().split())
  gr[a].append([b,c])
  gr[b].append([a,c])  
  
Q,K = map(int,input().split())

sta = deque([K])
dis = [10**10 for i in range(N+1)]
dis[K] = 0
sumi = [-1 for i in range(N+1)]

while len(sta) >= 1:
  a = sta.pop()
  sumi[a] += 1
  
  for j in gr[a]:
    if sumi[ j[0] ] != -1:
      continue
    else:
      sta.append(j[0])
      dis[j[0]] = dis[a] + j[1]
    
for i in range(Q):
  x,y = map(int,input().split())
  
  print(int(dis[x] + dis[y] ))
  

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define minvec(v) *min_element(all(v))
#define maxvec(v) *max_element(all(v))
#define sumvec(v) accumulate(all(v),0)
#define mapmax(v) v.rbegin()->first
#define mapmin(v) v.begin()->first
#define pb push_back
#define pf push_front
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))
#define zero(x,n) setw(x) << setfill('0') << n

typedef long long ll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;

const double pi = acos(-1.0);
const int mod=1000000007;
const int mod2=998244353;

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

template<class T>
inline bool chmax(T& a, T b){if(a<b){a=b;return true;} return false;}

template<class T>
inline bool chmin(T& a, T b){if(a>b){a=b;return true;} return false;}

void YES(bool b) {cout << (b?"YES\n":"NO\n");}
void Yes(bool b) {cout << (b?"Yes\n":"No\n");}
void yes(bool b) {cout << (b?"yes\n":"no\n");}
void Yay(bool b) {cout << (b?"Yay!\n":":(\n");}

long long powmod(long long a,long long b){
    long long c=1;
    while(b>0){
        if(b&1) c=a*c%mod;
        a=a*a%mod;
        b>>=1;
    }
    return c;
}

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

int main()
{
	ll n,m,l,r;
	cin >> n >> m;
	vll v(n+1);
	rep(i,m){
		cin >> l >> r;
		v[l]++;
		v[r+1]--;
	}
	rep(i,n) v[i+1]+=v[i];
	ll ans=0;
	for(auto&& e:v){
		if(e==m) ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <cctype>
#include <queue>
#include <set>
#include <list>
#define PI 3.141592653
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;
const ll INF=1e9+7;

int main(void) {
	string s;
	int n;
	cin >> n >> s;
	int cnt = 1;
	rep(i, 0, s.size()-1) {
		if (s[i] != s[i + 1])cnt++;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
using namespace std;
const int N = 250;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used: %.6lf(s)\n", ((double)TIME_END - TIME_START) / CLOCKS_PER_SEC);
    system("pause");
#endif
}
int n, m;ll s;
int a[N], b[N];
ll dp[55][5005];
struct edge
{
    int v, nxt, c, w;
} e[N];
struct Node
{
    ll u, c, t;
    bool operator<(const Node &x) const
    {
        return t > x.t;
    }
};
int head[N], ecnt;
inline void ad(int u, int v, int tim, int cost)
{
    e[++ecnt].v = v;
    e[ecnt].nxt = head[u];
    head[u] = ecnt;
    e[ecnt].c = cost;
    e[ecnt].w = tim;
}
priority_queue<Node> q;

void bfs()
{
    memarray(dp, inf);
    s = min(s, 2500ll);
    dp[1][s] = 0;
    q.push({1,s,0});
    while(!q.empty())
    {
        Node u = q.top();
        q.pop();
        int mn = min(u.c + a[u.u], 2500ll);
        if (dp[u.u][mn] > dp[u.u][u.c] + b[u.u])
        {
            dp[u.u][mn] = dp[u.u][u.c] + b[u.u];
            q.push({u.u, min(u.c + a[u.u], 2500ll), dp[u.u][mn]});
        }
        for (int i = head[u.u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            if (u.c < e[i].c)
                continue;
            if (dp[v][u.c - e[i].c] > dp[u.u][u.c] + e[i].w)
            {
                dp[v][u.c - e[i].c] = dp[u.u][u.c] + e[i].w;
                q.push({v, u.c - e[i].c, dp[v][u.c - e[i].c]});
            }
        }
    }
}

void solve()
{
    cin >> n >> m >> s;
    for (int i = 1; i <= m;++i)
    {
        int u, v, aa, bb;
        scanf("%d%d%d%d", &u, &v, &aa, &bb);
        ad(u, v, bb, aa);
        ad(v, u, bb, aa);
    }
    for (int i = 1; i <= n;++i)
        scanf("%d%d", &a[i], &b[i]);
    bfs();
    for (int i = 2; i <= n; ++i)
    {
        ll ans = LONG_LONG_MAX;
        for (int j = 0; j <= 2500; ++j)
            ans = min(ans, dp[i][j]);
        cout << ans << '\n';
    }
}

int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

Measured memory_bytes: 8548
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

int main(void)
{
    IOS
    string o; cin >> o;
    string e; cin >> e;
    string ans = "";
    REP(i,e.size()) {
        ans += o[i];
        ans += e[i];
    }
    if (o.size() > e.size()) ans += o.back();
    cout << ans << endl;

    return 0;
}

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

int main(){
    int a,b,r;
    string str="No";
    cin >> a >> b;
    r = stoi(to_string(a)+to_string(b));
    
    
    for (int i=0;i<330;i++){
        if (r==i*i){
            str = "Yes";
    }
    }
    cout << str << endl;
    }
    //sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});

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

int main(){

  string s;
  cin >> s;

  int n0 = 0;
  int n1 = 0;
  for(int i=0; i<s.size(); ++i){
    if(s[i] == '0') n0++;
    else n1++;
  }

  int ans = s.size() - abs(n0 - n1);
  cout << ans << endl;
  return 0;
}


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

// ?????¬???????????¬??????
#pragma region MACRO
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define PED cout << "\n"
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define ILP while(true)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#pragma endregion

// ???
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#pragma endregion

// Effective std
#pragma region ESTD
template<typename C, typename T> int count(C& c, T t) { return count(ALL(c), t); }
template<typename C, typename F> int count_if(C& c, F f) { return count_if(ALL(c), f); }
template<typename C, typename T> void erase(C& c, T t) { remove(ALL(c), t), c.end(); }
template<typename C> void remove(vector<C>& c, unsigned int index) { c.erase(c.begin()+index); }
template<typename C, typename T, typename U> void replace(C& c, T t, U u) { replace(ALL(c), t, u); }
template<typename C, typename F, typename U> void replace_if(C& c, F f, U u) { (ALL(c), f, u); }
template<typename C> void reverse(C& c) { reverse(ALL(c)); }
template<typename C> void sort(C& c) { sort(ALL(c)); }
template<typename C, typename Pred> void sort(C& c, Pred p) { sort(ALL(c), p); }
#pragma endregion

// ?????°
#pragma region CONST_VAL
constexpr int PI = (2*acos(0.0));
constexpr int EPS = (1e-9);
constexpr int MOD = (int)(1e9+7);
constexpr int INF = 100000000;
#pragma endregion

int w, h;
char a[21][21];
int dx[]{1,-1,0,0};
int dy[]{0,0,1,-1};
int cnt;

void dfs(int x, int y) {
    a[x][y] = 0;
    rep(i,4) {
        int nx = x + dx[i], ny = y + dy[i];
        if(0<=nx&&nx<h&&0<=ny&&ny<w&&a[nx][ny]=='.') {
            cnt++;
            dfs(nx, ny);
        }
    }
}

int main() {
    while(cin>>w>>h, w) {
        cnt = 1;
        rep(i,h) cin >> a[i];
        rep(i, h) rep(j,w) {
            if(a[i][j]=='@') {
                dfs(i,j);
                break;
            }
        }
        cout << cnt << endl;
    }
}

Measured memory_bytes: 3028
def c_remainder_minimization_2019(L, R):
    ans = float('inf')
    for i in range(L, min(R, L + 2019)):
        for j in range(i + 1, min(R + 1, L + 2020)):
            ans = min(ans, (i * j) % 2019)
            if ans == 0:
                return 0
    return ans

L, R = [int(i) for i in input().split()]
print(c_remainder_minimization_2019(L, R))

Measured memory_bytes: 3060
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const int INF = 1000000;
const double PI=3.14159265359;
const int MAX = 1000000;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; 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;
    }
}

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int main(){

  ll x,y;cin>>x>>y;
  // ll t[1000000];
  COMinit();


  // rep(i,0)

  // if(x<y)swap(x,y);
  ll mx=x/2,my=y/2;
  ll l=0,r=0;
  rep(i,0,mx+1){
    if((x-2*i)*2==(y-i)){
      l=i;
      r=(x-2*i);
      break;
    }
  }

  // t[0]=1,t[1]=1;
  // rep(i,2,l+r+1){
  //   t[i]=(t[i-1]*i)%mod;
  // }
  // out(((t[l+r]%mod)*(modinv(t[l],mod)*modinv(t[r],mod))%mod)%mod);
  if(l==0&&r==0){out(0);}
  else out(((fac[l+r]*finv[l]%mod)*finv[r]%mod)%mod);

  // cout<<l<<" "<<r<<endl;



  return 0;
}


Measured memory_bytes: 24188
#include <iostream>
#define rep(i,q) for(int i = 0; q > i; i++)
using namespace std;
int abbs(int way){
  if(way < 0){
    way *= -1;
  }
  return way;
}
int main(void){
  int max = 0;
  int N,K;
  cin >> N >> K;
  int x[N];
  rep(i,N) cin >> x[i];
  rep(i,N-K + 1){
    int tmp = 0;
    if(abbs(x[K + i - 1]) > abbs(x[i])){
      tmp += abbs(x[i]);
    } else {
      tmp += abbs(x[K + i - 1]);
    }
    tmp += x[K + i - 1] - x[i];
    if(i == 0 || max > tmp){
      max = tmp;
    }
  }
  cout << max << endl;
  return 0;
}

Measured memory_bytes: 640
N = int(input())
robo = [list(map(int, input().split())) for _ in range(N)]
robo_range = sorted(list(map(lambda x: [x[0]-x[1], x[0]+x[1]], robo)), key=lambda x: x[1])
border = -10**9-1
remain = 0

for r in robo_range:
    if r[0] >= border:
        border = r[1]
        remain += 1

print(remain)


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

int mod = 998244353;
    
int main(){
    int n, s;
    cin >> n >> s;
    int a[n];
    rep(i,n) cin >> a[i];
    int DP[n+1][s+1];
    rep(i,n+1){
        rep(j,s+1) DP[i][j] = 0;
    }

    DP[0][0] += 1;

    for(int i=1; i<n+1; i++){
        rep(j,s+1){
            DP[i][j] = (DP[i][j] + (2*DP[i-1][j]) % mod) % mod;
            if(j+a[i-1]<=s){
                DP[i][j+a[i-1]] = (DP[i][j+a[i-1]] + DP[i-1][j]) % mod;
            }
        }
    }

    cout << DP[n][s] << endl;
    return 0;
}

Measured memory_bytes: 38732
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define pp pair<int,int>
#define ll long long
#define ld long double
int inf=100000000;
ll INF=4000000000000000000;
ll MOD=1000000007;



int main() {
  int n;
  cin >> n;
  vector<int> a(4),b(4),c(n,inf);
  rep(i,4) cin >> a.at(i);
  rep(i,4) cin >> b.at(i);
  int ans=inf;
  c.at(0)=0;
  rep(i,4){
    for (int j=0;j<n;j++){
      if (c.at(j)==inf) continue;
      if (j+b.at(i)>=n) ans=min(ans,c.at(j)+a.at(i));
      else c.at(j+b.at(i))=c.at(j)+a.at(i);
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 3104
#include <stdio.h>
int main()
{
int m,f,r,sum;
while (1){
        scanf("%d%d%d",&m,&f,&r);
    if ((m==-1) && (f==-1) && (r==-1)){break;}
    if ((m==-1)|| (f==-1)){puts("F");}
    else{
        sum=m+f;

        if (sum>=80){puts("A");}
        else if ((sum>=65)&& (sum<80)){puts("B");}
        else if ((sum>=50)&& (sum<65)){puts("C");}
        else if (sum<30){puts("F");}
        else puts((r>=50)? "C":"D");
    }
}














return 0;}



Measured memory_bytes: 2108
#include <iostream>
#include <map>
#include <cstdio>

using namespace std;

int main(){
	int n, m;
	while(true){
		scanf("%d %d", &n, &m);
		if(n==0 && m==0){
			break;
		}

		//initialize map
		map<int, int> member;
		for(int i=1; i<=n; i++){
			member[i] = 0;
		}

		int number = 0;
		int check = 0;
		for(int i=1; ; i++){
			if(i > n){
				i = i - n;
			}
			if(member[i] == 0){
				check++;
				if(check == m){
					member[i] = ++number; check=0;
					// cout<<"index:"<<i<<" number:"<<+number<<endl; //debug
				}
			}
			if(number == n){
				break;
			}
		}

		for(int i=1; i<=n; i++){
			if(member[i] == n){
				printf("%d\n", i);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1236
//author: Harsh Nema
#include <bits/stdc++.h>
#define ll long long int
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll INF = 922337203685477;
#define pb push_back
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
int main()
{
    fastio;
    ll n=0,k=0;
    cin>>n>>k;
    ll r=0,s=0,p=0;
    cin>>r>>s>>p;
    string t;
    cin>>t;
    string ans="";
    for(ll i=0;i<k;++i) ans+='w';
    for(ll i=k;i<n;++i){
        if(t[i]==t[i-k] and ans[i-k]=='w')
            ans+='l';
		else
            ans+='w';
    }
    ll score=0;
	for(ll i=0;i<n;++i)
	if(ans[i]=='w'){
		if(t[i]=='r')
			score+=p;
		else if(t[i]=='p')
			score+=s;
		else
			score+=r;
	}
	cout<<score;
    return 0;
}


Measured memory_bytes: 640
from itertools import accumulate, chain, takewhile

def takeupto(p, xs):
    for x in xs:
        yield x
        if p(x): break

def last(xs):
    for x in xs:
        pass
    return x

n, h = map(int, input().split())
xs = [[int(x) for x in input().split()] for _ in range(n)]

a = max(x[0] for x in xs)
ys = sorted((x[1] for x in xs), reverse=True)
ns = takewhile(lambda y: y > a, ys)
ms = chain([0], accumulate(ns))
ps = takeupto(lambda m: m >= h, ms)
i, v = last(enumerate(ps))
r = max(0, h - v)
j = (r // a) + (r % a != 0)
print(i + j)

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

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int &ai: a) cin >> ai;
    sort(a.begin(), a.end());
    if (n % 2 == 0) {
        long long ans = 0;
        for (int i = 0; i < n / 2 - 1; i++) ans -= a[i] * 2;
        ans -= a[n / 2 - 1];
        ans += a[n / 2];
        for (int i = n / 2 + 1; i < n; i++) ans += a[i] * 2;
        cout << ans << endl;
    } else {
        long long ans1 = 0;
        for (int i = 0; i < n / 2 - 1; i++) ans1 -= a[i] * 2;
        ans1 -= a[n / 2 - 1];
        ans1 -= a[n / 2];
        for (int i = n / 2 + 1; i < n; i++) ans1 += a[i] * 2;
        long long ans2 = 0;
        for (int i = 0; i < n / 2; i++) ans2 -= a[i] * 2;
        ans2 += a[n / 2];
        ans2 += a[n / 2 + 1];
        for (int i = n / 2 + 2; i < n; i++) ans2 += a[i] * 2;
        cout << max(ans1, ans2) << endl;
    }
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std; 
int main(){
	int N, K; cin >> N >> K; 
	int A[100010] = {}; long long int B[100010] = {}; 
	for(int i = 0; i < N; i++){
		cin >> A[i] >> B[i]; 
	}
	long long int ans[35] = {}; // 下位ibit目で初めてK+1未満が確定
	for(int i = 0; i < 31; i++){
		if(!(((K+1) >> i) & 1)) continue; 
		int L = ((K+1) >> i) - 1; 
		for(int j = 0; j < N; j++){
			int c = (A[j] >> i); 
			bool ok = true; 
			for(int k = 0; k < 32 - i; k++){
				if(!((L >> k) & 1) && ((c >> k) & 1)) ok = false; 
			}
			if(ok) ans[i] += B[j]; 
		}
	}
	long long int mx = 0; 
	for(int i = 0; i < 31; i++){
		mx = max(mx, ans[i]); 
	}
	cout << mx << endl; 
}

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

using namespace std;

typedef long long ll;

#define FOR(a, b, i) for(int i=a; i<b; i++)
#define RFOR(a, b, i) for(int i=a; i>=b; i--)
#define PB push_back
#define MP make_pair
#define MOD 1e9+7
#define newline cout<<"\n"


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

    int n, k; cin>>n>>k;

    vector<int> a(n);
    sort(a.begin(), a.end());

    FOR(0, n, i) cin>>a[i];

    vector<vector<int> > dp(2, vector<int> (k+1));

    FOR(0, k+1, i)
    {
        dp[0][i] = 1;
        dp[1][i] = 0;
    }

    dp[0][0] = 1;
    dp[1][0] = 0;

    FOR(0, k+1, i)
    {
        FOR(0, n, j)
        {
            if(i-a[j]>=0)
            {
                dp[0][i] = min(dp[0][i], dp[1][i-a[j]]);
                dp[1][i] = max(dp[1][i], dp[0][i-a[j]]);
            }
        }
    }

    if(dp[0][k]) cout<<"Second";
    else cout<<"First";
    newline;





    return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,d,ok=0;
	cin>>a>>b>>c>>d;
	cout<<((c%b==0?c/b:c/b+1)<=(a%d==0?a/d:a/d+1)?"Yes":"No")<<endl;
	return 0;
}


Measured memory_bytes: 3612
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<set>

#define P 1000000007

using namespace std;

vector<vector<int>> v;
vector<int> c;

void dfs(int i, int n) {
  if(c[i] || n == 0) return;
  c[i] = true;
  for(int j = 0; j < v[i].size(); j++) {
    if(c[v[i][j]]) continue;
    dfs(v[i][j], n - 1);
  }
}

int main() {
  int n, m;
  cin >> n >> m;
  v.resize(n);
  c.resize(n);
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  dfs(0, 3);
  if(c[n - 1]) {
    cout << "POSSIBLE" << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}


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

Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e2 + 10;
LL multy(LL a, LL b)
{
	if (a > INF * INF / b) return INF * INF;
	else return a * b;
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	LL pa = 0, pb = 0;
	int n;
	cin >> n;
	while (n--)
	{
		LL a, b;
		cin >> a >> b;
		LL l = 1, r = INF * INF;
		LL ret = 1;
		while (l <= r)
		{
			LL mid = (l + r) / 2;
			if (pa <= multy(a, mid) && pb <= multy(b, mid)) ret = mid, r = mid - 1;
			else l = mid + 1;
		}
		pa = a * ret, pb = b * ret;
	}
	cout << pa + pb << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

struct BIT {
    int n;
    vi d;
    BIT(int n) : n(n + 1), d(n + 1) {}
    void add(int i, int x) {
        while (i < n) {
            d[i] += x;
            i += i & -i;
        }
    }
    int sum(int i) {
        int ret = 0;
        while (i > 0) {
            ret += d[i];
            i -= i & -i;
        }
        return ret;
    }
};
signed main() {
    int N;
    cin >> N;
    vi a(N);
    cin >> a;

    if (N == 1) {
        cout << a[0] << endl;
        return 0;
    }

    int L = 0, R = 1'000'000'001;
    while (R - L > 1) {
        int M = (L + R) / 2;
        map<int, int> cnt;
        cnt[0] = 1;
        int s = 0;
        int tmp = 0;
        BIT bit(2 * (N + 1));
        bit.add(0 + N + 1, 1);
        REP(i, N) {
            s += (a[i] < M ? -1 : 1);
            tmp += bit.sum(s + N + 1);
            bit.add(s + N + 1, 1);
        }
        if (tmp >= N * (N + 1) / 4) {
            L = M;
        } else {
            R = M;
        }
    }
    cout << L << endl;
    return 0;
}



Measured memory_bytes: 2660
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define MAXN 100

typedef long long ll;

const int INF=0x7fffffff;

using namespace std;

int n;

struct ANS{
	int x,y;
}ans[2*MAXN];
int tot=0;//次数

ll a[MAXN];

void front_back(){
	for(int i=2;i<=n;i++){ //从前往后看 
		if(a[i]<a[i-1]){
			a[i]+=a[i-1];
			tot++;
			ans[tot].x=i-1;//把i-1加到i上 
			ans[tot].y=i;
		}
	}
} 

void back_front(){//从后往前
	for(int i=n-1;i>=1;i--){//从后往前看 
		if(a[i]>a[i+1]){
			a[i]+=a[i+1];
			tot++;
			ans[tot].x=i+1;
			ans[tot].y=i;
		} 
	}
}



int main() {
	scanf("%d",&n);
	scanf("%lld",&a[1]);
	bool f=1;
	ll mx=a[1],mn=a[1];
	int sitmx=1,sitmn=1;
	for(int i=2;i<=n;i++){
		scanf("%lld",&a[i]);
		if(a[i]<a[i-1]&&f){//如果后面的更小则不满足条件 
			f=0;
		}
		if(a[i]>mx){//找最大值 及位置 
			mx=a[i];
			sitmx=i;
		}
		if(a[i]<mn){//找最小值 及位置 
			mn=a[i];
			sitmn=i;
		}
	}
	if(f){//已经满足条件 
		printf("0");
		return 0;
	}
	 
	if(mn>=0){//非负数 
		front_back();
	} 
	else if(mx<=0){//非正数 
		back_front();
	}
	else if(abs(mx)>abs(mn)){//最大值的绝对值更大 
		for(int i=1;i<=n;i++){//全部成为非负数 
			a[i]+=mx;
			tot++;
			ans[tot].x=sitmx;
			ans[tot].y=i;
		}
		front_back();
	}
	else {
		for(int i=1;i<=n;i++){//全部成为非正数 
			a[i]+=mn;
			tot++;
			ans[tot].x=sitmn;
			ans[tot].y=i;
		}
		back_front();
	}
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++){
		printf("%d %d\n",ans[i].x,ans[i].y);
	}
//	for(int i=1;i<=n;i++){
//		printf("%lld ",a[i]);
//	}
	return 0;
}

Measured memory_bytes: 128
N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))

time = 0
sum_t = sum(t)
velo_cap =[float("inf")]*(2*sum_t+1)
for i in range(N):
  start_t = time
  goal_t = time + 2*t[i]
  for s in range(0,2*sum_t+1):
    if s < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-goal_t))
  time += 2*t[i]
for s in range(2*sum_t+1):
  velo_cap[s] = min(velo_cap[s],2*sum_t-s,s)


print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)

Measured memory_bytes: 53084
N, M = map(int, input().split())
List = [list(map(int, input().split())) for i in range(M)]

ans = [' ']*M
num = [1]*N

for i, v in sorted(enumerate(List), key=lambda x: (x[1][0], x[1][1])):
    ans[i] = '{:06}{:06}'.format(v[0], num[v[0]-1])
    num[v[0]-1] += 1
    
print('\n'.join(ans))

Measured memory_bytes: 47760
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const ll MOD = 998244353;

ll modpow(ll x, ll n){
    ll res = 1;
    ll mul = x;
    while(n){
        if(n % 2) res = res * mul % MOD;
        mul = mul * mul % MOD;
        n /= 2;
    }
    return res;
}

struct Combination
{
    int maxn;
    vector<ll> fmemo;
    vector<ll> imemo;
    vector<ll> ifmemo;
    
    Combination(int maxn) : maxn(maxn){
        fmemo.resize(maxn + 1);
        imemo.resize(maxn + 1);
        ifmemo.resize(maxn + 1);
        for(ll i = 1; i <= maxn; i++){
            imemo[i] = modpow(i, MOD - 2);
        }
    }

    ll fact(ll n){
        if(n == 0) return 1;
        if(fmemo[n]) return fmemo[n];
        return fmemo[n] = n * fact(n - 1) % MOD;
    }

    ll ifact(ll n){
        if(n == 0) return 1;
        if(ifmemo[n]) return ifmemo[n];
        return ifmemo[n] = imemo[n] * ifact(n - 1) % MOD;
    }

    ll com(ll n, ll k){
        if(k > n) return 0;
        if(k == n || k == 0) return 1;
        return (fact(n) * ifact(k) % MOD) * ifact(n - k) % MOD;
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    int a[302][302];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) cin >> a[i][j];
    }
    bool b[302]{0};
    for(int j = 0; j < m; j++){
        for(int i = 0; i < n; i++){
            if(b[i]) continue;
            if(a[i][j]){
                b[i] = true;
                for(int k = i + 1; k < n; k++){
                    if(!a[k][j]) continue;
                    for(int l = j; l < m; l++) a[k][l] ^= a[i][l];
                }
                break;
            }
        }
    }
    int r = 0;
    for(int i = 0; i < n; i++) r += b[i];
    Combination com(n + m + 1);
    ll ans = 0;
    for(int j = 1; j <= r; j += 2){
        ans = (ans + com.com(r, j) * modpow(3, r - j) % MOD * modpow(2, n + m - r * 2)) % MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    if N == 1:
        print("1")
    elif N % 2 == 0:
        print(1 / 2)
    else:
        print(((N-1)/2 + 1) / N)


if __name__ == '__main__':
    main()


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

int main ( void )
{
	int N, result;
	cin >> N;
	if ( N % 2 == 0 ){
		result = N / 2;
	} else {
		result = ( N / 2 ) + 1;
	}
	cout << result << "\n";
	return 0;
}

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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 30;

// ====================================================================

int main() {
  int n;
  cin >> n;
  bool graph[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      graph[i][j] = true;
    }
  }

  for (int i = 0; i < n; i++) {
    graph[i][i] = false;  // 斜め線を引く
  }

  // 斜め線を引く
  int y = 0;
  for (int i = n / 2 * 2 - 1; i >= 0; i--) {
    graph[y][i] = false;
    y++;
  }

  // 数える
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (graph[i][j]) ans++;
    }
  }

  cout << ans / 2 << endl;

  // 答えを出力
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (graph[i][j]) {
        cout << i + 1 << " " << j + 1 << endl;
        graph[i][j] = false;
        graph[j][i] = false;
      }
    }
  }
}


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

int main() {
	string s;
	cin >> s;
	string a = s.substr(0,1);
	string b = s.substr(s.size()-1,1);
	char str1[100];
	sprintf(str1, "%d", s.size()-2);
	string c = a + str1 + b;
	cout<< c;
}

Measured memory_bytes: 256
s=list(map(int,input()))
an=0

for i in range(1,len(s)):
    if s[0]==0:
        if i%2==0 and s[i]==1:
            an+=1
        elif i%2==1 and s[i]==0:
            an+=1
    else:
        if i%2==0 and s[i]==0:
            an+=1
        elif i%2==1 and s[i]==1:
            an+=1

print(an)

Measured memory_bytes: 3956
#include <iostream>
#include <vector>
#include <map>

using namespace std;

typedef long long ll;

ll gcd(ll x, ll y) {
  while (y != 0) {
    ll r = x % y; x = y; y = r;
  }
  return x;
}


vector<pair<ll, int> > prime_factor(ll n) {
  vector<pair<ll, int> > ret;

  for (ll i = 2; i*i <= n; i++) {
    if (n % i != 0) { continue; }
    int exp = 0;
    while (n % i == 0) {
      exp++;
      n /= i;
    }
    ret.push_back( make_pair(i, exp) );
  }

  if (n != 1) {
    ret.push_back( make_pair(n, 1) );
  }

  return ret;
}


int main() {
  ll a, b;
  cin >> a >> b;

  ll g = gcd(a, b);

  cout << prime_factor(g).size() + 1 << endl;

  return 0;
}

Measured memory_bytes: 256