akhauriyash/Code-Regression huggingface dataset:
/*
 * atcoder/abc129/e.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
#define MOD 1000000007
template <class T> void madd(T &a, T b) {
  a += b;
  a %= MOD;
}

/*
 * aとbの２進数第d桁をそれぞれ(c, d)とする.
 * a + b = a xor b なので、(1, 1)は繰り上がりが発生するので無し.
 * 1) Lの上からd桁目が1の場合: 0が1通り, 1が2通り
 * 2) L               0      :
 *    i) d以前にa+b<Lが確定している場合: 0が1通り, 1が2通り
 *    ii) そうでない場合               : 0 1通り
 */
string L;
int N;
ll dp[100100][2];
ll rec(int d = 0, bool less = false) {
  ll &cc = dp[d][less];
  if (~cc) return cc;
  if (d == N) return cc = 1;

  ll ways = 0;
  int b = L[d] - '0';
  if (b) {
    madd(ways, 1 * rec(d+1, true));
    madd(ways, 2 * rec(d+1, less));
  } else {
    if (less) madd(ways, 3 * rec(d+1, less));
    else madd(ways, rec(d+1, less));
  }
  return cc = ways;
}
void solve() {
  cin >> L;
  N = L.size();
  memset(dp, -1, sizeof(dp));
  cout << rec() << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 8320
#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
#include <cstdio>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i++)

int a[4];
int main(){
    string input;
    cin >> input;

    rep(i,4) a[i] = input[i] - '0';
    

    rep(x, 8) {
        int sum = a[0];
        string s;
        s += (char)('0' + a[0]);

        rep(i, 3) {
            if (x & (1<<i)) {
                sum += a[i+1];
                s += '+';
                s += (char)('0' + a[i+1]);
            } else {
                sum -= a[i+1];
                s += '-';
                s += (char)('0' + a[i+1]);
            }
        }
        if (sum == 7) {
            s += '=';
            s += '7';
            cout << s << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
#define pi pair<int,int>
using namespace std;
int main(){
	string s , t ; 
	cin>> s >> t ; 
	int dp[s.length()+ 1][t.length()+1] ; 
	memset(dp , 0 , sizeof dp) ;
	for(int i = 0 ; i <=(int)s.length() ; ++i){
		for(int j = 0 ; j <=(int)t.length() ;++j){
			if(i == 0 || j == 0)
			    dp[i][j] = 0 ;
		   else if(s[i-1] == t[j-1])
		   dp[i][j] = dp[i-1][j-1] + 1 ;
		   else 
		   dp[i][j] = max(dp[i-1][j] , dp[i][j-1] );
	   }
   }
   
   string x  = ""; 
   int n = s.length() ,  m = t.length() ; 
     while( m > 0 && n > 0){
		 
		 if(dp[n][m] > max(dp[n-1][m] , dp[n][m-1]) ){
			 x = x + s[n-1] ;  
			 n-- , m-- ; 
		 }
		 else if(dp[n][m] == dp[n][m-1])
			       m-- ; 
	    else
	        n-- ; 
		}
		reverse(x.begin() , x.end()) ; 
		cout<<x<<endl;
	}
			 
		 
		 


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

string S[55];
ll T[55];

int main() {
    ll N;
    cin >> N;
    REP(i, N) {
        cin >> S[i] >> T[i];
    }
    string X;
    cin >> X;
    ll ans = 0;
    bool sleep = false;
    REP(i, N) {
        if (sleep)
            ans += T[i];
        if (S[i] == X)
            sleep = true;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
num = [[[0 for i in range(10)] for i in range(3)] for i in range(4)]

n = int(input())
for i in range(n):
    b, f, r, v = map(int, input().split())
    num[b-1][f-1][r-1] += v

for b in range(4):
    for f in range(3):
        print(" " + " ".join(map(str, num[b][f])))
    if b < 3:
        print("#"*20)



Measured memory_bytes: 5608
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
const ll mod = (ll)1e9 + 7;
const ll INF = (ll)2e18;
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;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>vector<T> make_vector(size_t a){return vector<T>(a);}

class DColoringEdgesOnTree {
public:
    int N;
    vector<int> next[110000];
    int color[110000] = {0};
    unordered_map<string, int> ans;
    int val = 1;

    void dfs(int now, int before = 1) {
        vector<int> ac;
        if (now == 1) {
            int number = 1;
            for (int temp : next[now]) {
                if (color[temp] != 0) continue;
                val = max(val, number);
                color[temp] = number++;
                ans[to_string(now) + " + " + to_string(temp)] = color[temp];
                ans[to_string(temp) + " + " + to_string(now)] = color[temp];
                ac.push_back(temp);
            }
        } else {
            int number = 1;
            for (int temp : next[now]) {
                if (color[temp] != 0) continue;
                if (number == ans[to_string(before) + " + " + to_string(now)]) ++number;
                val = max(val, number);
                color[temp] = number++;
                ans[to_string(now) + " + " + to_string(temp)] = color[temp];
                ans[to_string(temp) + " + " + to_string(now)] = color[temp];
                ac.push_back(temp);
            }
        }
        for (int temp : ac) {
            dfs(temp, now);
        }
    }

	void solve(std::istream& in, std::ostream& out) {
	    in >> N;
	    color[1] = -1;
	    vector<pair<int, int>> record(N);
	    rep(i, N - 1) {
	        in >> record[i].first >> record[i].second;
	        next[record[i].first].push_back(record[i].second);
            next[record[i].second].push_back(record[i].first);
	    }
	    dfs(1);
	    out << val << endl;
	    rep(i, N - 1) {
	        out << ans[to_string(record[i].first) + " + " + to_string(record[i].second)] << endl;
	    }
	}
};


int main() {
	DColoringEdgesOnTree solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 37540
#include <iostream>
#include <set>
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    
    ll place[N + 1];
    // place[i]...値iのaにおけるindex
    
    for (int i = 1; i <= N; ++i) {
        ll a;
        cin >> a;
        place[a] = i;
        // 保持するのはindexなので、ここが普通と逆なことに注意
    }

    ll ans = 0;
    set<ll> used = {0, N + 1};
    // すでに見た要素のindexを保持する
    
    for (int i = 1; i <= N; ++i) {
        ll r, l;
        
        auto itr = used.lower_bound(place[i]);
        r = *itr;
        // lower_boundで右端を調べる(upper_boundでもいい)
        l = *(--itr);
        // その1個手前が左端
        
        ans += i * (place[i] - l) * (r - place[i]);
        used.insert(place[i]);
    }

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

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll n;
  cin >> n;
  vl a(n);
  vl ans(n);
  ll sum = 0;
  REP(i,n){
    ll ai;
    cin >> ai;
    a[i] = ai;
    if(i%2==0) sum += ai;
    else sum -= ai;
  }
  ans[0] = sum;
  FOR(i,1,n){
    ans[i] = a[i-1]*2 - ans[i-1];
  }
  REP(i,n){
    cout << ans[i] << " ";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  int n,T,a,b,flag=0;
  cin >>n;
  rep(i,n){
    int t,x,y;
    cin>>t>>x>>y;
    if (t%2==1) {
      if (abs(x)+abs(y)>t || (abs(x)+abs(y))%2==0) {
        flag+=1;
        break;
      }
      else if (i!=0 && abs(x-a)+abs(y-b)>t-T) {
        flag+=1;
        break;
      }
    }
    else{
      if (abs(x)+abs(y)>t || (abs(x)+abs(y))%2==1) {
        flag+=1;
        break;
      }
      else if (i!=0 && abs(x-a)+abs(y-b)>t-T) {
        flag+=1;
        break;
      }
    }
    T=t;
    a=x;
    b=y;  
  }
  if (flag==0) {
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void fast()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
}
int main()
{
    fast();
    long long a,b;
    cin>>a>>b;
    if(a==1 || b==1)
        cout<<1;
    else
        cout<<(b/2)*((a+1)/2+a/2)+(b%2)*(a+1)/2;
    return 0;
}


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

struct UnionFind{
    vector<int> par;
    
    UnionFind(int n) : par(n,-1) { }
    void init(int n) { par.assign(n,-1); }
    
    int root(int x){
        if(par[x]<0) return x;
        else return par[x]=root(par[x]);
    }
    
    bool issame(int x,int y){
        return root(x)==root(y);
    }
    
    bool merge(int x,int y){
        x=root(x);
        y=root(y);
        if(x==y) return false;
        if(par[x]>par[y]) swap(x,y);
        par[x]+=par[y];
        par[y]=x;
        return true;
    }
    
    int size(int x){
        return -par[root(x)];
    }
};

int main(){
    int N,K,L;
    cin>>N>>K>>L;
    UnionFind uf1(N),uf2(N);
    for(int i=0;i<K;i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        uf1.merge(a,b);
    }
    for(int i=0;i<L;i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        uf2.merge(a,b);
    }
    
    using pint=pair<int,int>;
    map<pint,int> ma;
    for(int v=0;v<N;v++){
        pint p(uf1.root(v),uf2.root(v));
        ma[p]++;
    }
    for(int v=0;v<N;v++){
        pint p(uf1.root(v),uf2.root(v));
        cout<<ma[p]<<" ";
    }
}



Measured memory_bytes: 13568
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
int main() {
  int H,W,i,j,b,sum;
  b=H+W-2;
  cin>>H>>W;
  sum=0;
  char a[H][W];
  int B[H][W]={0};
  for(i=0;i<H;i++){
  for(j=0;j<W;j++){
  cin>>a[i][j];
  }
  }
  for(i=0;i<H;i++){
    b=H+W-2;
  for(j=0;j<W;j++){
  if(a[i][j]=='#'){
  B[i][j]=0;
    b=0;
  }else{
    b=min(b+1,H+W-2);
B[i][j]=b;
  
  }
      
  }
  }
  for(i=0;i<H;i++){
    b=H+W-2;
      for(j=0;j<W;j++){
  if(a[i][W-j-1]=='#'){
  B[i][W-j-1]=0;
    b=0;
  }else{
    b=min(b+1,H+W-2);
B[i][W-j-1]=min(b,B[i][W-j-1]);
   
  }
      
  }
    
   
  }

  
   for(i=0;i<W;i++){
      b=H+W-2;
  for(j=1;j<H;j++){
  if(a[j][i]=='#'){
  B[j][i]=0;
    b=0;
  }else{
    b=min(min(b+1,H+W-2),B[j-1][i]+1);
B[j][i]=min(b,B[j][i]);
 
  }
      
  }
     b=H+W-2;
      for(j=1;j<H;j++){
  if(a[H-j-1][i]=='#'){
  B[H-j-1][i]=0;
    b=0;
  }else{
    b=min(b+1,H+W-2);
B[H-j-1][i]=min(min(b,B[H-j-1][i]),B[H-j][i]+1);
   
  }
      
  }
   }
  for(i=0;i<H;i++){
  for(j=0;j<W;j++){
   
  sum=max(sum,B[i][j]);
  }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 5120
n=int(input())
# 数値を文字列に変換
s = str(n)
# １文字ずつ数値化し配列にする。
array = list(map(int, s))
n=array[-1]
if n==3:
  print("bon")
elif n==0 or n==1 or n==6 or n==8:
  print("pon")
else:
  print("hon")

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

const ll minf = -(ll)1e18;

int main()
{
	int n;
	cin >> n;
	vector<ll> A(n), sum(n + 1);
	for (int i = 0; i < n; i++) {
		cin >> A[i];
		sum[i + 1] = sum[i] + A[i];
	}
	vector<map<ll, int>> v(n + 1);
	vector<int> pre(n + 1);
	v[0][minf] = 0;
	for (int i = 0; i < n; i++) {
		map<int, ll> tmp;
		int tt = 0, ts = 0;
		for (int j = i; j >= 0; j--) {
			auto it = v[j].lower_bound(sum[i + 1] - sum[j]);
			if (it != v[j].begin()) {
				--it;
				if (it->second + 1 > tt || (it->second + 1 == tt && sum[i + 1] - sum[j] < ts)) {
					tt = it->second + 1;
					ts = sum[i + 1] - sum[j];
					pre[i + 1] = j;
				}
				if (tmp.count(it->second + 1)) {
					tmp[it->second + 1] = min(tmp[it->second + 1], sum[i + 1] - sum[j]);
				}
				else {
					tmp[it->second + 1] = sum[i + 1] - sum[j];
				}
			}
		}
		vector<pair<ll, int>> hoge;
		for (auto p : tmp) {
			hoge.emplace_back(p.second, p.first);
		}
		sort(hoge.begin(), hoge.end());
		ll ma = minf;
		for (auto p : hoge) {
			if (p.second > ma) {
				ma = p.second;
				v[i + 1][p.first] = p.second;
			}
		}
	}
	int res = 0;
	for (auto p : v[n]) {
		res = max(res, p.second);
	}
	cout << res << endl;
	int it = n;
	vector<int> vs;
	while (pre[it] != 0) {
		vs.push_back(pre[it]);
		it = pre[it];
	}
	reverse(vs.begin(), vs.end());
	for (int i = 0; i < (int)vs.size(); i++) {
		if (i != 0) cout << ' ';
		cout << vs[i];
	}
	cout << endl;
	return 0;
}



Measured memory_bytes: 10992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
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; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;
 
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll 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(void)
{
    ll n;
    cin >> n;
    ll m;
    cin >> m;
    vector<ll> a(m);
    ll sum = 0;
    REP(i, m)
    {
        cin >> a[i];
        sum += a[i];
    }

    if(n - sum < 0){
        cout << -1 << endl;
    }
    else{
        cout << n - sum << endl;
    }

    return 0;
}

Measured memory_bytes: 3708
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for (int i = 0; i < n; ++i)
#define REP(i,k,n) for (int i = k; i <= n; ++i)
#define REPR(i,k,n) for (int i = k; i >= n; --i)
#define pb push_back
#define F first
#define S second
#define I insert
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define debug1(a) cout<<" "<<#a<<" : "<<a<<"\n"
#define debug2(a,b) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<"\n"
#define debug3(a,b,c) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<"\n"
#define debug4(a,b,c,d) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<" "<<#d<<" : "<<d<<"\n"
#define INF (int)10000000000000000
#define PI (double)3.14159265358979
// #define M 421412341324321
#define MOD 1000000007

map <int, int> m;
const int p = 1e6+4;
bool A[p];

int modpower(int n, int k)
{
	int res = 1;
	while(k>0)
	{
		if (k&1) res = (res*n)%MOD;
		k>>=1;
		n = (n*n)%MOD;
	}
	return res;
}

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	int n;
	cin>>n;
	int a[n];
	memset(A, 0, sizeof(A));
	for (int i=0;i<n;++i)
	{
		cin>>a[i];
	}
	for(int i=0;i<n;++i)
	{
		int num = a[i];
		if (A[a[i]])
			continue;
		for (int j=2;j*j<=num;++j)
		{
			if ((num%j)==0)
			{
				int c=0;
				while((num%j)==0)
				{
					num/=j;
					c++;
				}
				m[j] = max(m[j], c);
			}
		}
		if (num>1)
		{
			m[num] = max(m[num], 1ll);
		}
		A[a[i]] = 1;
	}
	int ans = 0;
	int l = 1;
	for (auto j:m)
	{
		l*=modpower(j.F, j.S);
		l%=MOD;
	}
	for (int i=0;i<n;++i)
	{
		int x = l*modpower(a[i], MOD-2);
		x%=MOD;
		ans+=x;
		ans%=MOD;
	}	
	cout<<ans<<"\n";



	return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(b)-1;i>=(a);--i)
#define ALL(a) a.begin(),a.end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    int a = 0;
    for (auto &tp : mp) {
        if (a) os << ", "; a = 1;
        os << tp;
    }
    return os << "}";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << ":" << p.second;
    return os;
}


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

    for (;;) {
        int T, D, L; cin >> T >> D >> L;
        if (T == 0) break;

        vi sum(T+1);
        FOR(i, 1, T+1) {
            int x; cin >> x;
            if (x >= L) {
                ++sum[i];
                --sum[min(i + D, T)];
            }
        }
        REP(i, T) {
            sum[i+1] += sum[i];
        }

        int ans = 0;
        for (int s : sum) {
            if (s) ++ans;
        }
        cout << ans << endl;
    }

    return 0;
}



Measured memory_bytes: 3536
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,i,j,w;
    cin>>n>>w;
    long long int profit[n][w+1];
    for(i=0;i<n;i++)
    for(j=0;j<w+1;j++)
    profit[i][j]=0;
    vector<pair<long long int,long long int> > v(n);
    for(i=0;i<n;i++)
    cin>>v[i].first>>v[i].second;
    for(i=0;i<n;i++)
    {
        for(j=0;j<=w;j++)
        {  if(i==0)
           {if(j>=v[i].first)
            profit[i][j]=v[i].second;
            else
            profit[i][j]=0;}
            else if(j==0)
            profit[i][j]=0;
            else
            {if(j-v[i].first>=0)
             profit[i][j]=max(profit[i-1][j],profit[i-1][j-v[i].first]+v[i].second);
             else
             profit[i][j]=profit[i-1][j];
            }
        }
    }
    cout<<profit[n-1][w];
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;

string solve() {
    size_t k; cin >> k;
    string s; cin >> s;
    if (s.size() > k) {
        return s.substr(0, k) + "...";
    }

    return s;
}

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

	cout << solve() << endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
using namespace std;

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

int main(){

  int n, q;
  long long S[100010], T[50010];
  int count = 0;
  int j;
  long long left, right, key, mid;

  cin >> n;
  REP( i, n ){
    cin >> S[i];
  }
  cin >> q;
  REP( i, q ){
    cin >>T[i];
  }


  REP( i, q ){
  key = T[i];
  left = 0;
  right = n;
    while( left < right ){
      mid = ( left + right ) / 2;
      if( S[mid] == key ){
        count++;
        break;
      } else if( key < S[mid] ){
        right = mid;
      } else {
        left = mid + 1;
      }
    }
  }

  cout << count << endl;



  return 0;

}

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/


Measured memory_bytes: 4244
#include <bits/stdc++.h>
#define FR first
#define SE second
#define MOD 1000000007

using namespace std;

typedef long long ll;
typedef pair<int,int> pr;

ll pow2[2005];

void pre(int n) {
  pow2[0]=1;
  for(int i=1;i<=n;i++) pow2[i]=pow2[i-1]*2LL%MOD;
}

vector <pr> ee[2005];

int fa[1005][15],maxn[1005][15];
int dep[1005];

void dfs(int x) {
  for(int i=0;i<ee[x].size();i++)
    if (ee[x][i].FR!=fa[x][0]) {
    	int u=ee[x][i].FR;
    	fa[u][0]=x;maxn[u][0]=ee[x][i].SE;
		dep[u]=dep[x]+1;
		for(int j=1;j<15;j++) {
			fa[u][j]=fa[fa[u][j-1]][j-1];
			maxn[u][j]=max(maxn[u][j-1],maxn[fa[u][j-1]][j-1]);
		}
		dfs(u);
	}
}

int query(int x,int y) {
  if (dep[x]<dep[y]) swap(x,y);
  int ans=0,d=dep[x]-dep[y];
  for(int i=0;i<15;i++)
    if ((d>>i)&1) {
    	ans=max(ans,maxn[x][i]);
    	x=fa[x][i];
	}
  if (x==y) return ans;
  for(int i=14;i>=0;i--)
    if (fa[x][i]!=fa[y][i]) {
    	ans=max(ans,maxn[x][i]);
    	ans=max(ans,maxn[y][i]);
    	x=fa[x][i];
    	y=fa[y][i];
	}
  ans=max(ans,maxn[x][0]);
  ans=max(ans,maxn[y][0]);
  return ans;
} 

namespace SETS {

int fa[1005];

void init(int n) {
  for(int i=1;i<=n;i++) fa[i]=i;
}

int find_father(int x) {
  return (fa[x]==x)?x:fa[x]=find_father(fa[x]);
}

bool check(int x,int y) {
  x=find_father(x);y=find_father(y);
  return x!=y;
}

void merge(int x,int y) {
  x=find_father(x);y=find_father(y);
  if (x==y) return;
  fa[x]=y;
}

}

struct Edge {
  int s,t,v;
  Edge() {}
  Edge(int a,int b,int c):s(a),t(b),v(c) {}
  bool operator < (const Edge & b) const {return v<b.v;}
};

Edge e[2005];
bool in[2005];

int val[2005];

int main() {
  int n,m;
  ll X;
  scanf("%d%d%lld",&n,&m,&X);
  pre(m);
  for(int i=1;i<=m;i++) {
  	int x,y,z;
  	scanf("%d%d%d",&x,&y,&z);
  	e[i]=Edge(x,y,z);
  }
  sort(e+1,e+m+1);
  SETS::init(n);
  ll s=0;
  for(int i=1;i<=m;i++)
    if (SETS::check(e[i].s,e[i].t)) {
    	int u=e[i].s,v=e[i].t;
    	in[i]=1;
    	s+=e[i].v;
    	SETS::merge(u,v);
    	ee[u].push_back(pr(v,e[i].v));
    	ee[v].push_back(pr(u,e[i].v));
	}
  if (s>X) {
  	puts("0");
  	return 0;
  }
  int ans=0;
  if (s==X) ans=(ans+(pow2[n-1]-2LL+MOD)*pow2[m-n+1])%MOD;
  dfs(1);
  int cnt=0;
  for(int i=1;i<=m;i++)
    if (!in[i]) val[++cnt]=e[i].v-query(e[i].s,e[i].t);
  sort(val+1,val+cnt+1);
  for(int i=1;i<=cnt;i++)
    if (s+val[i]==X) ans=(ans+2LL*pow2[cnt-i])%MOD;
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 512
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,maxx=-1,minn=1e9;
int a[100010],num[100010];
bool flag=0;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		num[a[i]]++;
		maxx=max(maxx,a[i]);
		minn=min(minn,a[i]);
		if(a[i]!=a[i-1]&&i>=2)flag=1;
	}
	if(maxx-minn>1){printf("No");return 0;}
	if(flag)
	{
		if(2*(maxx-num[minn])<=num[maxx]&&maxx>num[minn])printf("Yes");
		else printf("No");
	}
	else
	{
		int x=a[1];
		if(x==1||x==n-1||x==n/2)printf("Yes");
		else printf("No");
	}
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>

using namespace std;

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

int main() {
  while (true) {
    int n, m, p;
    cin >> n >> m >> p;
    if (n == 0 && m == 0 && p == 0) break;
    int board[10][10][10] = {};
    int win = 0;
    rep (i, p) {
      int x, y, z;
      cin >> x >> y;
      --x; --y;
      for (z = 0; board[x][y][z] != 0; ++z);
      board[x][y][z] = i % 2 * 2 - 1;
      rep (ddx, 3) rep (ddy, 3) rep (ddz, 3) {
	int dx = ddx - 1;
	int dy = ddy - 1;
	int dz = ddz - 1;
	if (dx == 0 && dy == 0 && dz == 0) continue;
	int count = 1;
	for (int j = 1; ; ++j) {
	  if (x + dx * j < 0 || n <= x + dx * j) break;
	  if (y + dy * j < 0 || n <= y + dy * j) break;
	  if (z + dz * j < 0 || n <= z + dz * j) break;
	  if (board[x + dx * j][y + dy * j][z + dz * j] != board[x][y][z]) break;
	  ++count;
	}
	for (int j = -1; ; --j) {
	  if (x + dx * j < 0 || n <= x + dx * j) break;
	  if (y + dy * j < 0 || n <= y + dy * j) break;
	  if (z + dz * j < 0 || n <= z + dz * j) break;
	  if (board[x + dx * j][y + dy * j][z + dz * j] != board[x][y][z]) break;
	  ++count;
	}
	if (count >= m && win == 0) {
	  if (i % 2) {
	    cout << "White" << " " << i + 1 << endl;
	  } else {
	    cout << "Black" << " " << i + 1 << endl;
	  }
	  win = board[x][y][z];
	}
      }
    }
    if (win == 0) cout << "Draw" << endl;
  }
  return 0;
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,m,d;
  cin>>n>>m>>d;
  string s[n];
  for(int i=0;i<n;i++) cin>>s[i];
  int ans=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(s[i][j]=='#') continue;
      if(i+d<=n){
	bool f=1;
	for(int k=0;k<d;k++) f&=s[i+k][j]=='.';
	if(f) ans++;
      }
      if(j+d<=m){
	bool f=1;
	for(int k=0;k<d;k++) f&=s[i][j+k]=='.';
	if(f) ans++;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
const ll INF=99999999999999999;
ll a,b,c,d,e,f,ans=0;
int main(){
    ll n;
    string s;
    cin>>n;
    cin>>s;
    a=0;
    b=0;
    rep(i,n){
        if(s[i]=='R')a++;
        else b++;
    }
    if(a>b)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>

#define ff first
#define ss second

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

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

    int n,k;
    cin>>n>>k;
    vector<int> cnt(n);
    for(int i=0; i<k; i++){
        int d;
        cin>>d;
        for(int j=0; j<d; j++){
            int tmp;
            cin>>tmp;
            cnt[tmp-1]+=1;
        }
    }
    int answer=0;
    for(int i=0; i<n; i++) if(cnt[i]==0) answer+=1;
    cout<<answer;

    return 0;
}


Measured memory_bytes: 3656
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let (n,k) = {
        let t = read_vec::<i64>();
        (t[0],t[1])
    };
    let mut v = vec![];
    for _ in 0..n{
        let (a,b) = {
            let t = read_vec::<i64>();
            (t[0],t[1])
        };
        v.push((a,b));
    }
    v.sort();
    let mut ans = 0;
    let mut sum = 0;
    for  &(a,b) in &v{
        if sum >= k{
            break;
        }
        sum += b;
        ans = a;
    }
    println!("{}",ans);
}

Measured memory_bytes: 6396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7/*998244353*/;
const ll INF = 1LL << 60;
ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);
//
int main(){
    int n;
    cin >> n;
    vector<int> left(n), right(n);
    for(int i = 0; i < n; i++) cin >> left[i] >> right[i];
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());
    if(n % 2){
        cout << (right[(n - 1) / 2] - left[(n - 1) / 2]) + 1;
    }else{
        ll l1 = left[n / 2 - 1];
        ll r1 = right[n / 2 - 1];
        ll l2 = left[n / 2];
        ll r2 = right[n / 2];
        double dl = (double)(l2 + l1) / 2.0;
        double dr = (double)(r2 + r1) / 2.0;
        ll ans = (ll)((dr - dl) / 0.5) + 1;
        //cout << l1 << " " << r1 << " " << l2 << " " << r2 << " ";
        cout << ans;
    }
}

Measured memory_bytes: 4692
#include <bits/stdc++.h>
using namespace std;
#define M 998244353

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    map<int,int> m;
    for(int i=0;i<n;i++)
    {
        m[v[i]]++;
    }
    vector<long long> dp(n);
    if(m[0]!=1 || v[0]!=0)
        cout<<0;
    else
    {
        int flag=0;
        dp[0]=1;
        int l=1;
        for(auto i: m)
        {
            if(i.first==0)
                continue;
            if(i.first!=l)
                {
                    flag=1;
                    break;
                }
            int x=m[i.first-1];
            long long w=1;
            for(int j=0;j<i.second;j++)
            {
                w=(w*x)%M;
            }
            dp[l]=(dp[l-1]*w)%M;
            l++;
        }
        if(flag)
            cout<<0;
        else
            cout<<dp[l-1];
    }
    return 0;
}


Measured memory_bytes: 6144
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int main(){
    long long int x;
    cin>>x;
    long long int div11;
     int sur;
    sur =x%11;
    div11 =x/11;
    if(6<sur){
        cout<<(2*div11)+2<<endl;
    }else if(1<=sur && sur<=6){
        cout<<(2*div11)+1<<endl;
    }else{
         cout<<(2*div11)<<endl;
    }
    return 0;
}


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


int main(){
    int n,a,b,count=0;
    cin >> n >> a >> b;
    for(int i=0;i<n;i++){
        int x,y;
        cin >> x >> y;
        if(x>=a && y>=b){
            count++;
        } 
    }
    cout << count;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<vector<int>> a(N, vector<int>(N, 0)), c(N, vector<int>(N + 1, 0));
    for (int i = 0, L, R; i < M; i++) {
        cin >> L >> R;
        a[L - 1][R - 1]++;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            c[i][j + 1] = c[i][j] + a[i][j];
        }
    }
    for (int i = 0, p, q; i < Q; i++) {
        cin >> p >> q;
        int s = 0;
        for (int j = p - 1; j < q; j++) {
            s += c[j][q] - c[j][p - 1];
        }
        cout << s << endl;
    }
}

Measured memory_bytes: 2944
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

main()
{
  int N,i,j;
  char **W,z;

  scanf("%d",&N);
  W = malloc(sizeof(char*)*N);
  for(i=0;i<N;i++)
    W[i] = malloc(sizeof(char)*10);

  for(i=0; i<N; i++)
    {
      for(j=0; j<10; j++)
        W[i][j] = '\0';
      scanf("%s",W[i]);
      for(j=0; j<i; j++)
        if(strcmp(W[i],W[j])==0)
          {
            printf("No\n");
            exit(0);
          }
      if(i!=0&&z!=W[i][0])
        {
          printf("No\n");
          exit(0);
        }
      for(j=0;W[i][j]!='\0';j++)
        z = W[i][j];
    }
  printf("Yes\n");
}

Measured memory_bytes: 128
n = int(input())
f = [0]*(n+1)
for i in range(2,n+1):
    a = i
    for j in range(2,i+1):
        while a % j == 0:
            f[j] += 1
            a //= j
def number(m):
    c = 0
    for i in range(n):
        if f[i] >= m - 1:
            c += 1
    return c
print(number(75) + number(25)*(number(3) - 1) + number(15)*(number(5) - 1) 
+ number(5)*(number(5) - 1)*(number(3) - 2)//2)


Measured memory_bytes: 3064
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
def nt(s):
	if s == "Blue":
		return "Red"
	return "Blue"
N = int(input())
A = ["" for i in  range(N*2)]

print(" ".join(["?"]+[str(i) for i in range(1,N+1)]), flush=True)

s = input()

t = 0
b = N

while b-t > 1:
	m = (t+b)//2
	print(" ".join(["?"]+[str(i) for i in range(1,m+1)]+[str(i) for i in range(N+1,2*N-m+1)]), flush=True)
	r = input()
	if s == r:
		b = m
	else:
		t = m

A[b-1] = s
A[N*2-b] = nt(s)
known = [str(b), str(N*2-b+1)]


ask = [str(i) for i in range(1,b+1)]+[str(i) for i in range(N+1,2*N-b+2)]
asks = copy.copy(ask)
for a in ask:
	if a in known:
		continue
	asks.remove(a)
	print(" ".join(["?"]+asks), flush=True)
	r = input()
	if r != s:
		A[int(a)-1] = s
		known.append(a)
	else:
		A[int(a)-1] = nt(s)
	asks.append(a)

ask = [str(i) for i in range(b,N+1)]+[str(i) for i in range(2*N-b+1,N*2+1)]

asks = copy.copy(ask)
for a in ask:
	if a in known:
		continue
	asks.remove(a)
	print(" ".join(["?"]+asks), flush=True)
	r = input()
	if r != s:
		A[int(a)-1] = s
		known.append(a)
	else:
		A[int(a)-1] = nt(s)
	asks.append(a)
print("! "+"".join(["B" if r == "Blue" else "R" for r in A]))

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

int main( void )
{
    int x,a,b;
    cin >> x >> a >> b;
    
    int ans = x - a - ((x - a) / b) * b;
    
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		String ans = "x";
		if (a + b == 15) {
			ans = "+";
		} else if (a * b == 15) {
			ans = "*";
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 21844
#include<iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include<bitset>
#include<string>
#include <deque>
#include<queue>
#include <iomanip>
#include<map>
#include <random>
#include<type_traits>
using namespace std;

long long int A[10000][10000];

int main() {
	long long int N, M, Q,a,b;
	cin >> N >> M >> Q;
	for (long long int i = 0; i < M; i++) {
		cin >> a >> b;
		A[a][b] += 1;
	}
	for (long long int i = 1; i <= N; i++) {
		for (long long int j = 1; j <= N; j++) {
			A[i][j] += A[i][j - 1];
		}
	}
	for (long long int i = 1; i <= N; i++) {
		for (long long int j = 1; j <= N; j++) {
			A[j][i] += A[j-1][i];
		}
	}
	for (long long int i = 0; i < Q; i++) {
		cin >> a >> b;
		cout << A[b][b] + A[a - 1][a - 1] - A[a - 1][b] - A[b][a - 1] << endl;
	}
}


Measured memory_bytes: 40064
#include<iostream>
#include<cstdio>
#include<cmath>
typedef long long ll;
using namespace std;
ll n;
int a[100010];
int dis[100010];
int main()
{
    ll sum=0;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    ll k;
    if((2*sum%(n*(n+1)))!=0)
    {
        printf("NO");
        return 0;
    }
    k=2*sum/n/(n+1);
    for(int i=0;i<n;i++)
    {
        if(i==n-1)
            dis[i]=a[0]-a[i];
        else
            dis[i]=a[i+1]-a[i];
    }
    for(int i=0;i<n;i++)
    {
        if(k-dis[i]<0||(k-dis[i])%n!=0)
        {
            printf("NO");
            return 0;
        }
    }
    printf("YES");
    return 0;
}

Measured memory_bytes: 1024
import collections
N = int(input())
A = list(map(int,input().split()))
a = collections.Counter(A)
alist = a.most_common()
alen = len(a)
alist.sort(reverse=True)
kari = 0
flag = 0
for i in range(alen):
    if alist[i][1] >= 4 and kari == 0:
        print(alist[i][0]*alist[i][0])
        flag = 1
        break
    elif alist[i][1] >= 2:
        if kari > 0:
            print(kari*alist[i][0])
            flag = 1
            break
        else:
            kari = alist[i][0]
    else:
        pass
if flag == 0:
    print(0)

Measured memory_bytes: 21668
#include <iostream>

using namespace std;

int main(){
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;
    if(W >= x+r && x >= 0 && H >= y+r && y >= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3096
/**
 *    author:  tourist
 *    created: 05.01.2020 11:08:10       
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll solve(ll n, ll a, ll b, ll m) {
  if (b == 0) return n * (a / m);
  if (a >= m) return n * (a / m) + solve(n, a % m, b, m);
  if (b >= m) return n * (n - 1) / 2 * (b / m) + solve(n, a, b % m, m);
  return solve((a + b * n) / m, (a + b * n) % m, m, b);
}

pair<long long, long long> GetKBest(int k, long long cx, long long cy) {
  long long low = 0, high = 1;
  while (true) {
    long long cnt = solve(high / cx + 1, high % cx, cx, cy) + (high / cx + 1);
    if (cnt >= k) {
      break;
    }
    low = high + 1;
    high = 2 * high;
  }
  while (low < high) {
    long long mid = (low + high) >> 1;
    long long cnt = solve(mid / cx + 1, mid % cx, cx, cy) + (mid / cx + 1);
    if (cnt >= k) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  long long sx = 0, sy = 0;
  for (int x = 0; x * cx <= high; x++) {
    long long cc = (high - x * cx) / cy + 1;
    sx += cc * x;
    sy += cc * (cc - 1) / 2;
  }
  return {sx, sy};
}

bool Solvable(int k, int X, int Y) {
  auto a = make_pair(-1LL, -1LL), b = a;
  long long total = (long long) 1e9 + 7;
  long long low = 0, high = total;
  while (low < high) {
    long long mid = (low + high) >> 1;
    auto p = GetKBest(k, total - mid, mid);
    if (p.first <= X && p.second <= Y) {
      return true;
    }
    if (p.first >= X && p.second >= Y) {
      return false;
    }
    if (p.first < X) {
      a = p;
      low = mid + 1;
    } else {
      b = p;
      high = mid;
    }
  }
  return (a.second * (b.first - X) + b.second * (X - a.first) <= Y * (b.first - a.first));
}

int main() {
  int X, Y;
  cin >> X >> Y;
  if (X > Y) {
    swap(X, Y);
  }
  int low = 3, high = (int) 2e6;
  while (low < high) {
    int mid = (low + high + 1) >> 1;
    if (Solvable(mid, X, Y)) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  cout << low - 1 << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1LL<<60
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;

struct edge{
	int to,rev;
	ll cap,cost;
	edge(int t,int c,int co,int r){
		to=t;
		cap=c;
		cost=co;
		rev=r;
	}
};

struct mincostflow{
	vector<edge> G[2005];
	ll h[2005];
	ll dist[2005];
	int prevv[2005],preve[2005];

	void add_edge(int from,int to,int cap,int cost){
		G[from].push_back(edge(to,cap,cost,G[to].size()));
		G[to].push_back(edge(from,0,-cost,G[from].size()-1));
	}

	ll min_cost_flow(int s,int t,int f,int V){
		ll res=0;
		fill(h,h+V,0);
		while(f>0){
			priority_queue<P,vector<P>,greater<P> > que;
			fill(dist,dist+V,INF);
			dist[s]=0;
			que.push(P(0,s));
			while(que.size()){
				P p=que.top();
				que.pop();
				int v=p.second;
				if(dist[v]<p.first)continue;
				for(int i=0;i<G[v].size();i++){
					edge &e=G[v][i];
					if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
						dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
						prevv[e.to]=v;
						preve[e.to]=i;
						que.push(P(dist[e.to],e.to));
					}
				}
			}
			if(dist[t]==INF)return -1;
			for(int v=0;v<V;v++){
				h[v]+=dist[v];
			}
			ll d=f;
			for(int v=t;v!=s;v=prevv[v]){
				d=min(d,G[prevv[v]][preve[v]].cap);
			}
			f-=d;
			res+=d*h[t];
			for(int v=t;v!=s;v=prevv[v]){
				edge &e=G[prevv[v]][preve[v]];
				e.cap-=d;
				G[v][e.rev].cap+=d;
			}
		}
		return res;
	}
};

mincostflow mi;
int cnt[1001];

int main(void){
	int n;
	scanf("%d",&n);
	ll res=0;
	for(int i=0;i<n;i++){
		int k;
		scanf("%d",&k);
		for(int j=0;j<k;j++){
			int t,c;
			scanf("%d%d",&t,&c);
			t--;
			mi.add_edge(i,t,50000,c);
			cnt[t]++;
			cnt[i]--;
			res+=c;
		}
	}
	int S=n,T=n+1;
	int fsum=0;
	for(int i=0;i<n;i++){
		if(cnt[i]>0){
			mi.add_edge(S,i,abs(cnt[i]),0);
		}else{
			mi.add_edge(i,T,abs(cnt[i]),0);
			fsum+=abs(cnt[i]);
		}
	}
	mi.add_edge(S,0,50000,0);
	res+=mi.min_cost_flow(S,T,fsum,T+1);
	printf("%lld\n",res);
	return 0;
}


Measured memory_bytes: 6068
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, k = I()
print(min(n % k, abs(n % k - k)))

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	int L=in();
	double V=L/3.0;
	out(V*V*V);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int> 

int main(){
  ll N, A, B; cin >> N >> A >> B;
  ll ans;
  if (N==1){
    if (A==B) ans = 1;
    else ans = 0;
  }
  else {
    if (A>B) ans = 0;
    else ans = (N-2)*(B-A)+1;
  }

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

Measured memory_bytes: 256
package main

import (
  "fmt"
  "math"
  "sort"
)

func main() {
  var n int
  fmt.Scan(&n)
  p := Points{}
  for i:=0;i<n;i++ {
    var x,y float64
    fmt.Scan(&x,&y)
    p = append(p,Point{x,y,i})
  }
  h := p.GetHull()
  if h.Len() == 1 {
    fmt.Println(0)
    return
  } else if h.Len() == 2 {
    fmt.Println(0.5*h[0].distance(h[1]))
    return
  }
  ans := 1e18
  for _,p0 := range h {
    for _,p1 := range h {
      if p1 == p0 { continue }
      for _,p2 := range h {
        if p2 == p0 || p2 == p1 { continue }
        var x,y float64
        a0 := p0.angle(p2,p1)
        if a0 < 0.0 { a0 += 2*math.Pi }
        a1 := p1.angle(p0,p2)
        if a1 < 0.0 { a1 += 2*math.Pi }
        a2 := p2.angle(p1,p0)
        if a2 < 0.0 { a2 += 2*math.Pi }
        if a0 >= 0.5*math.Pi {
          x = 0.5*(p1.x+p2.x)
          y = 0.5*(p1.y+p2.y)
        } else if a1 >= 0.5*math.Pi {
          x = 0.5*(p2.x+p0.x)
          y = 0.5*(p2.y+p0.y)
        } else if a2 >= 0.5*math.Pi {
          x = 0.5*(p0.x+p1.x)
          y = 0.5*(p0.y+p1.y)
        } else {
          a := p1.distance2(p2)
          b := p2.distance2(p0)
          c := p0.distance2(p1)
          A := a*(b+c-a)
          B := b*(c+a-b)
          C := c*(a+b-c)
          x = (A*p0.x+B*p1.x+C*p2.x)/(A+B+C)
          y = (A*p0.y+B*p1.y+C*p2.y)/(A+B+C)
        }
        p := Point{x,y,-1}
        r := 0.0
        for _,q := range h { r = math.Max(r,p.distance(q)) }
        ans = math.Min(ans,r)
      }
    }
  }
  fmt.Printf("%.20f\n",ans)
}

type Point struct {
  x,y float64
  id int
}
func(p Point) equals(t Point) bool { return p.x == t.x && p.y == t.y }
func(p Point) angle(sta Point,end Point) float64 {
  ax := sta.x - p.x
  bx := end.x - p.x
  ay := sta.y - p.y
  by := end.y - p.y
  return math.Atan2(ax*by-ay*bx,ax*bx+ay*by)
}
func(p Point) distance2(t Point) float64 {
  dx := p.x - t.x
  dy := p.y - t.y
  return dx*dx+dy*dy
}
func(p Point) distance(t Point) float64 {
  return math.Sqrt(p.distance2(t))
}
type Points []Point
func(ps Points) Len() int { return len(ps) }
func(ps Points) Swap(i,j int) { ps[i],ps[j] = ps[j],ps[i] }
func(ps Points) Less(i,j int) bool {
  if ps[i].x == ps[j].x {
    if ps[i].y == ps[j].y { return ps[i].id < ps[j].id }
    return ps[i].y < ps[j].y
  }
  return ps[i].x < ps[j].x
}
func(ps Points) GetHull() Points {
  sort.Sort(sort.Reverse(ps))
  now := ps[0]
  prv := Point{now.x,now.y-1,-1}
  hull := Points{now}
  for {
    var minagl,maxdst float64
    minagl = 2*math.Pi
    maxdst = 0
    nxt := ps[0]
    for _,p := range ps {
      if p.equals(now) { continue }
      var angle,dstnc float64
      angle = now.angle(prv,p)
      dstnc = now.distance(p)
      if angle < 0 { angle += 2*math.Pi }
      if angle < minagl && angle >= math.Pi {
        minagl = angle
        nxt = p
        maxdst = dstnc
      } else if angle == minagl && dstnc > maxdst {
        nxt = p
        maxdst = dstnc
      }
    }
    if nxt.equals(hull[0]) { break }
    hull = append(hull,nxt)
    prv = now
    now = nxt
  }
  return hull
}

Measured memory_bytes: 512
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

if (a[1] - a[0]) == (b[1] - b[0]) == (c[1] - c[0]) and (a[2] - a[1]) == (b[2] - b[1]) == (c[2] - c[1]):
    print('Yes')
else:
    print('No')

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

int main(){
  int N,M,p,k=INT_MAX;
  cin >> N >> M;
  int a[N],b[N],c[M],d[M],x[N];
  for(int i=0;i<N;i++){
    cin >> a[i] >> b[i];
  }
  for(int i=0;i<M;i++){
    cin >> c[i] >> d[i];
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      p=(abs(a[i]-c[j]) + abs(b[i]-d[j]));
      if(p < k){
        k=p;
        x[i]=j+1;
      }
    }
    k=INT_MAX;
  }
  for(int i=0;i<N;i++){
    cout << x[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define llong long long
using namespace std;

const int N = 2e5;
int a[N+3],b[N+3],c[N+3];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	a[1] = 1; for(int i=1; i<=n; i++) b[i] = 1; for(int i=2; i<=n; i++) c[i] = 1;
	for(int i=1; i<=m; i++)
	{
		int x,y; scanf("%d%d",&x,&y);
		if(b[x]>0)
		{
			if(b[x]==1)
			{
				if(a[x]) {a[y] = 1; a[x] = 0;}
				if(c[x]) {c[y] = 1; c[y] = 0;}
			}
			else
			{
				c[y] |= c[x];
				a[y] |= a[x];
			}
			b[x]--; b[y]++;
		}
	}
	int ans = 0;
	for(int i=1; i<=n; i++) if(a[i]) {ans++;}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1280
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner scanner = new Scanner(System.in);

		int N = scanner.nextInt();

		int[] scannerArrayA = new int[N];
//		int[] scannerArrayB = new int[N];
		int[] scannerArrayC = new int[N];

		int ans = 0;

//		int maxNumber = 0;
//		int number = 0;

		for (int index = 0; index < N; index++) {
//			number = scanner.nextInt();
			scannerArrayA[index] = scanner.nextInt();
		}

		for (int index = 0; index < N; index++) {
//			number = scanner.nextInt();
//			scannerArrayB[index] = scanner.nextInt();
			ans += scanner.nextInt();
		}

		for (int index = 0; index < N-1; index++) {
//			number = scanner.nextInt();
			scannerArrayC[index] = scanner.nextInt();
		}

		int tmp = scannerArrayA[0];

		for(int index = 0; index < N - 1; index++) {
			if((tmp + 1) == scannerArrayA[index + 1]) {
				ans+=scannerArrayC[scannerArrayA[index] - 1];
			}
			tmp = scannerArrayA[index + 1];
		}



		log(ans);
	}

	private static void log(int str) {
		System.out.println(str);
	}

}



Measured memory_bytes: 23380