akhauriyash/Code-Regression huggingface dataset:
s=input()
n=len(s)
dp=[[0 for i in range(4)]for j in range(n+1)]
for i in range(n,-1,-1):
  for j in range(3,-1,-1):
    if i==n:
      if j==3:
        dp[i][j]=1
      else:
        dp[i][j]=0
    else:
      if j==3:
        if s[i]=='?':
          dp[i][j]=dp[i+1][j]*3
        else:
          dp[i][j]=dp[i+1][j]
      else:
        if s[i]=='?':
          dp[i][j]=dp[i+1][j]*3+dp[i+1][j+1]
        elif (j==0 and s[i]=='A') or (j==1 and s[i]=='B') or (j==2 and s[i]=='C'):
          dp[i][j]=dp[i+1][j]+dp[i+1][j+1]
        else:
          dp[i][j]=dp[i+1][j]
    dp[i][j]%=10**9+7
print(dp[0][0])

Measured memory_bytes: 55644
#include <bits/stdc++.h>
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define SORTR(v,n) sort(v, v+n, greater<int>());
// #define int long long    // %d=>%lld
#define pb push_back
#define INF (1e9+7)
#define llINF 1e17
#define EPS 1e-9
#define pi acos(-1)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> piii;
typedef pair<ll, pll> plll;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

void UnionFindInit(UnionFind uf,int a){
    for(int i=0;i<a;i++){
        uf.data.pb(i);
    }
}

struct edge{
    int u,v,cost;
    bool operator < ( const edge& right ) const {
        return cost < right.cost;
    }
};



const int MAX_V = pow(10,5);
UnionFind uf(MAX_V);
const int MAX_E = pow(10,5)*5;
int V,E;
int s,t,c;
edge G[MAX_E];


int kruskal(){
    SORT(G,E);
    UnionFindInit(uf,V);
    int res= 0;
    for(int i = 0;i < E;i++){
        if(!uf.findSet(G[i].u,G[i].v)){
            uf.unionSet(G[i].u,G[i].v);
            res += G[i].cost;
        }
    }
    return res;
}



signed main(){

    cin >> V;

    pii px[MAX_V];
    pii py[MAX_V];

    for(int i = 0;i < V;i++){
        cin >> px[i].first;
        cin >> py[i].first;
        px[i].second=i;
        py[i].second=i;

    }

    SORT(px,V);
    SORT(py,V);

    for(int i = 0;i < V-1;i++){
        G[i] = (edge){px[i].second,px[i+1].second,px[i+1].first-px[i].first};
        E++;
    }

    for(int i = 0;i < V-1;i++){
        G[i+V-1] = (edge){py[i].second,py[i+1].second,py[i+1].first-py[i].first};
        E++;
    }

    int ans = kruskal();
    cout <<  ans << endl;

    return 0;
}



Measured memory_bytes: 7040
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() {
	int n;
	cin >> n;
	ll dp[2][105];
	int a[2][105];
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < n; j++) {
			cin>>a[i][j];
		}
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum += a[0][i];
		dp[0][i] = sum;
	}
	dp[1][0] = dp[0][0] + a[1][0];
	for (int i = 1; i < n; i ++) {
		dp[1][i] = max(dp[1][i - 1] + a[1][i], dp[0][i] + a[1][i]);
	}
	cout << dp[1][n - 1] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp(a, b) make_pair(a, b)
#define pb(t) push_back(t)
#define ft first
#define sc second
#define pt(num) cout << num << "\n"
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define chmax(a, b) (a<b ? a=b : 0)
#define chmin(a, b) (a>b ? a=b : 0)
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 101010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

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

int main(void) {
    ll N;
    cin >> N;
    ll i;
    ll a[MAX];
    for(i=0; i<N; i++) {
        cin >> a[i];
    }
    
    ll ans=a[0];
    for(i=0; i<N; i++) {
        ans=gcd(ans, a[i]);
    }
    pt(ans);
}





Measured memory_bytes: 1024
N, M = gets.split.map(&:to_i)

Mod = 10 ** 9 + 7

def fact(n)
  (1..n).inject(1){ |res, i| res * i % Mod }
end

t = [2, 1, 0]
a = ( N - M ).abs
a = 2 if a >= 2

puts t[a] * fact(N) * fact(M) % Mod

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

using namespace std;

bitset<20>vf;

int main()
{
    int x;
    for(int i=1;i<=4;i++)
    {
        cin>>x;
        vf[x]=1;
    }

    if(vf[1]==1 && vf[9]==1 && vf[7]==1 && vf[4]==1)cout<<"YES";
    else cout<<"NO";
    return 0;
}


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

#define ll long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int mod = 1e9 + 7;
const int MAX = 2e5 + 1;

vector<int> adj[MAX];

bool visited[MAX];   // For DFS

vector<int> comp;   // For storing the connected components

int ct = 0, mxm = INT_MIN;

void addEdge(int x, int y)
{
	adj[x].push_back(y);
	adj[y].push_back(x);
}

void dfs(int v)
{
	visited[v] = true;
	comp.push_back(v);

	for (int u : adj[v])
	{
		if (!visited[u])
		{
			dfs(u);
		}
	}
}

void find_comps(int n)
{
	for (int i = 1; i <= n ; ++i)
	{
		visited[i] = false;
	}

	for (int i = 1; i <= n ; ++i)
	{
		if (!visited[i])
		{
			comp.clear();
			dfs(i);
			/*cout << "Component: " ;
			for (size_t j = 0; j < comp.size(); ++j)
			{
				cout << ' ' << comp[j];
			}
			cout << endl;*/
			mxm = max(mxm, (int) comp.size());
			ct += 1;
		}
	}
}

int main()
{
	//IOS
	int t = 1;
	//cin >> t;
	while(t--)
	{
		int nodes, edges;      // Nodes are numbered from 1 to N
		cin >> nodes >> edges;
		while(edges--)
		{
			int x, y;
			cin >> x >> y;
			addEdge(x, y);
		}
		find_comps(nodes);
		//cout << "No. of connected components = " << ct << endl;
		cout << mxm;
	}
	return 0;
}


Measured memory_bytes: 24556
#include<stdio.h>
int main()
{
int i, j, n, m, a[1000], sum, max;

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

for(i = 0; i < n ; i++)
{
scanf("%d",&a[i]);
}
max = 0;
for(i = 0; i < n ; i++)
{
for(j = i+1; j<n;j++)
{
sum = a[i]+a[j];
if(sum>max&&sum<=m)
max=sum;
}
}
if(max==0)
printf("NONE\n");
else
printf("%d\n",max);
}
return 0;
}


Measured memory_bytes: 2144
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

using namespace std;

#define fori(x) for (int i = 0; i < x; ++i)
#define forj(x) for (int j = 0; j < x; ++j)

typedef long long ll;

const int INF = 2e9 + 5;
const int alength=100100;

int main() {
	int t,x;
	cin>>t>>x;
	cout<<fixed<<setprecision(10);
	cout<<(float)t/(float)x;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    string a,b;
    cin >>a >>b;
    if(a.length()>b.length()){
        cout <<"GREATER"<<endl;
    }
    else if(a.length()<b.length()){
        cout <<"LESS"<<endl;
    }
    else if(a>b){
        cout <<"GREATER"<<endl;
    }
    else if(a<b){
        cout <<"LESS"<<endl;
    }
    else{
        cout <<"EQUAL"<<endl;
    }
    return 0;
}

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

int aaa(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 sum;
  int c;
  for (int i = 0; i <= N; i++) {
    c = aaa(i);
    if(c >= A && c <= B) {
      sum += i;
    }
  }
  cout << sum << endl;
}

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

#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(int i = m, i##_len = (n); i < i##_len; ++i)
#define all(x) (x).begin(), (x).end()
#define clr(ar, val) memset(ar, val, sizeof(ar))
#define sbp(p, n) rep(i, n) { int a, b; scanf("%d %d", &a, &b); p[i] = make_pair(a, b); }
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
using namespace std;

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

int main(void)
{
  int n, q, l, r;
  int ac[100001] = {}, j = 0;
  char s[100001] = {};
  cin >> n >> q;
  cin >> s;
  int x = 0;
  ac[0] = 0;
  rep(i, strlen(s)){
    if(s[i] == 'A' && s[i + 1] == 'C') x++;
    ac[i + 1] = x;
  }
  rep(i, q){
    cin >> l >> r; 
    cout << ac[r - 1] - ac[l - 1] << endl;
  }
  return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
int main(){
    ll n;cin >> n;
    ll num=sqrt(n);
    ll ans=0;
    //cout << num << endl;
    for(ll i=1;i<=num;i++){
        if(n%i==0){
            ll nn = n/i;
            if(nn-1>i){
                ans+=nn-1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    string ans = "Yes";
    if (a == b && a != c && b!= c){
        cout << ans << endl;
    }else if (b == c && b != a && c != a){
        cout << ans << endl;
    }else if (c == a && a != b && c != b){
        cout << ans << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
/////////////////// TYPES & MACROS ///////////////////////////////
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define vv vector
#define exist(s,e) (s.find(e)!=s.end())
using ll=long long int; using dd=double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
typedef vector<int> vi;
ll INFLL=(ll)2e18, MOD=1'000'000'007;
const int INF=0x3f3fffff ;
/////////////////// DEBUG /////////////////////////////////////////
#define D(x) cerr<<#x<<" is: "<<x<<'\n';
#define DD(x,y) cerr<<"("<<#x<<","<<#y<<") are: "<<x<<" "<<y<<'\n';
/////////////////// VARIABLES & FUNCTIONS//////////////////////////
vv<vi> adj; vi vis; vi level;
// int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1},dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};
int dx8[]={-1,1,2,2,1,-1,-2,-2}, dy8[]={2,2,1,-1,-2,-2,-1,1};
inline ll mexp(ll x,ll n,ll m){ll res=1;while(n){if(n&1)res=(res*x)%m;n>>=1;x=((x%m)*(x%m))%m;}return res;}
inline bool ispow2(ll x){ return x && (!(x&(x-1)));}
inline ll gcd(ll x, ll y){ pll p{x,y}; while(p.ss) p={p.ss,p.ff%p.ss}; return p.ff;}


/////////////////// MAIN STARTS //////////////////////////////////
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
cout<<fixed;cerr<<fixed; cout<<setprecision(10); cerr<<setprecision(3);
// random_device rd; mt19937 genr(rd());

#ifdef DEBUG
  auto tStart = chrono::system_clock::now(); //freopen("op.txt","w",stdout);
#endif

int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
int dx=x2-x1, dy=y2-y1;
cout<< x2-dy<<' '<<y2+dx <<' '<<x1-dy<<' '<<y1+dx <<'\n'; 

#ifdef DEBUG
  auto diff=chrono::system_clock::now()-tStart;
  cerr<<"\nExecution time: "<<chrono::duration<dd,milli>(diff).count()<<" ms.\n";
#endif
return 0;
}


Measured memory_bytes: 256
//https://atcoder.jp/contests/abc162/tasks/abc162_d
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
const ll LINF = 0x1fffffffffffffff;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
#if LOCAL&01
  std::ifstream in("./test/sample-2.in");
  //std::ifstream in("./input.txt");
  std::cin.rdbuf(in.rdbuf());
#else
  cin.tie(0);
  ios::sync_with_stdio(false);
#endif
  ll N; cin>>N;
  string S; cin>>S;
  vector<vector<ll>> rgb(3,vector<ll>());
  constexpr int R=0,G=1,B=2;
  FOR(i,0,S.size()){
    ll p=i+1;
    char c = S.at(i);
    if(c=='R'){
      rgb[R].push_back(p);
    }else if(c=='G'){
      rgb[G].push_back(p);
    }else if(c=='B'){
      rgb[B].push_back(p);
    }
  }
  ll ans=rgb[R].size() * rgb[G].size()*rgb[B].size();
  ll tmp=0;
  FOR(i,0,N){
    FOR(s,1,N){
      ll p0=i,p1=i+s,p2=i+2*s;
      if(p1>=N||p2>=N)break;
      if(S.at(p0)!=S.at(p1) && S.at(p1)!=S.at(p2) && S.at(p0)!=S.at(p2)){
        //dump(p0,p1,p2);
        ++tmp;
      }
    }
  }
  dump(ans, tmp);
  cout<<ans-tmp<<endl;
#if 0
  ll ans=0;
  for(const auto& r:rgb[R]){
    for(const auto& g:rgb[G]){
      for(const auto& b:rgb[B]){
        vector<ll> tmp={r,g,b};
        sort(tmp.begin(),tmp.end());
        if(tmp[1]-tmp[0]!=tmp[2]-tmp[1]){ //j-i != k-j
          ++ans;
        }
      }
    }
  }
  cout<<ans<<endl;
#endif
  return 0;
}

Measured memory_bytes: 3660
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define mp make_pair
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<30)
#define LLINF (1LL<<60)
//#define MOD 998244353
#define MOD 1000000007
#define PI 3.14159265358979
using ll = long long;
using namespace std;

int main(){
    int n,k,value[1005];
    cin>>n>>k;
    rep(i,n){
        cin>>value[i];
    }
    sort(value, value+n);
    int ans=0;
    rep(i,k){
        ans+=value[i];
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<size_t I,class H,class...T>struct TupleReaderWriter{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple_cat(tuple<H>(v),TupleReaderWriter<sizeof...(T)-1,T...>::r(i));}static void w(ostream&o,tuple<H,T...>&t,string d){TupleReaderWriter<I-1,H,T...>::w(o,t,d);o<<d<<get<I>(t);}};
template<class H,class...T>struct TupleReaderWriter<0,H,T...>{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple<H>(v);}static void w(ostream&o,tuple<H,T...>&t,string d){o<<get<0>(t);}};
template<class...T>istream&operator>>(istream&i,tuple<T...>&t){t=TupleReaderWriter<sizeof...(T),T...>::r(i);return i;}
template<class...T>ostream&operator<<(ostream&o,tuple<T...>&t){string delim=" ";TupleReaderWriter<sizeof...(T)-1,T...>::w(o,t,delim);return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(auto&x:v)i>>x;return i;}
template<class T>ostream&operator<<(ostream&o,vector<T>&v){string delim="";for(auto&x:v)o<<delim<<x,delim=" ";return o;}
template<class T>using rev_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>using vector2d=vector<vector<T>>;
struct fixprec{int x;fixprec(int d):x(d){}};
ostream&operator<<(ostream&o,fixprec f){return o<<fixed<<setprecision(f.x);}
void R_YESNO(bool p) { cout << (p ? "YES" : "NO") << endl; }
void R_YesNo(bool p) { cout << (p ? "Yes" : "No") << endl; }
int main() {
    int N;
    cin >> N;
    vector<i64> A(N), ans(N, 0);
    for(i64 &x : A) cin >> x;
    deque<int> deq;
    for(int i = N - 1; i >= 0; i--) {
        while(!deq.empty() && A[i] > A[deq.front()]) {
            deq.pop_front();
        }
        deq.push_front(i);
    }
    priority_queue<i64> q;
    int cur, prev = N;
    // prevと同じ高さの山の数
    i64 m = 0;
    while(!deq.empty()) {
        // 取る必要のある石の数
        i64 S = 0;

        cur = deq.back(); deq.pop_back();
        // 右側の山を、取る山キューに追加
        if(prev >= 0) {
            for(int i = cur; i < prev; i++) {
                q.push(A[i]);
            }
        }
        if(prev < N) {
            ans[prev] += (A[prev] - A[cur]) * m;
        }
        while(q.size() && q.top() >= A[cur]) {
            S += q.top() - A[cur];
            q.pop();
            m++;
        }
        if(prev < N) ans[prev] += S;
        prev = cur;
    }
    ans[prev] = accumulate(WHOLE(A), - accumulate(WHOLE(ans), i64(0)));
    for(i64 x : ans) cout << x << endl;
    return 0;
}



Measured memory_bytes: 3072
#include "bits/stdc++.h"
 
using namespace std;
 
int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<char>> mass(H, vector<char>(W));
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> mass.at(i).at(j);
        }
    }
 
    vector<bool> row(H, false);
    vector<bool> col(W, false);
 
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            if(mass.at(i).at(j) == '#'){
                row.at(i) = true;
                col.at(j) = true;
            }
        }
    }
    for(int i = 0; i < H; i++){
        if(row.at(i)){
            for(int j = 0; j < W; j++){
                if(col.at(j)) cout << mass.at(i).at(j);
            }
            cout << endl;
        }
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <bitset>

using namespace std;
const int MAX_N = 3000;
double dp[MAX_N][MAX_N];
double p[MAX_N];

int main() {

  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  int N;  cin >> N;
  for (int i = 0; i < N; i++) cin >> p[i];

  dp[0][0] = 1.0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= i; j++) {
      dp[i+1][j+1] += dp[i][j] * p[i];
      dp[i+1][j]   += dp[i][j] * (1 - p[i]);
    }
  }
  
  double res = 0.0;
  for (int j = N/2 + 1; j <= N; ++j) res += dp[N][j];
  printf("%0.12lf\n", res);
  return 0;
}


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

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.141592653589793238462643383279;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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; }

int MSB(int n) {
    n |= (n >> 1);
    n |= (n >> 2);
    n |= (n >> 4);
    n |= (n >> 8);
    n |= (n >> 16);
    return n - (n >> 1);
}

int main(void){
    int N,K; cin >> N >> K;
    VI A(N), B(N); REP(i,N) cin >> A[i] >> B[i];
    ll sum = 0; REP(i,N) sum += B[i];
    vector<bool> buy(N,true);
    ll ans = 0;
    REP(j,30){
        if(K>>(29-j) & 1){
            ll tmp = sum;
            REP(i,N){
                if(A[i]>>(29-j) & 1 && buy[i])
                    tmp -= B[i];
            }
            chmax(ans, tmp);
        }
        else{
            REP(i,N){
                if(A[i]>>(29-j) & 1 && buy[i]){
                    buy[i] = false;
                    sum -= B[i];
                }
            }
        }
    }
    chmax(ans, sum);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    long double x; cin>>x;
    ll c = 100;

    int ans = 0;
    while (c < x) {
        c = 1.01*c;
        ans++;
    }

    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3728
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int lli;
typedef pair<lli, lli> pll;
const lli inf = 1e18;

int main(){
	int n;
	cin >> n;
	int m = n%100;
	n /= 100;
	if(1<=n and n<=12 and 1<=m and m<=12){
		cout << "AMBIGUOUS" << endl;
	}else if(1<=n and n<=12){
		cout << "MMYY" << endl;
	}else if(1<=m and m<=12){
		cout << "YYMM" << endl;
	}else{
		cout << "NA" << endl;
	}
    return 0;
}

Measured memory_bytes: 256
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0

using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

/*-----------------------------------------ここからコード-----------------------------------------*/


int main() {
	
	int a[4];
	scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]);
	sort(a, a + 4);
	printYN(a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9);
	
	Please AC;
}


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

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

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);std::cout<<std::fixed<<std::setprecision(10);
    ll N;
    cin >> N;
    N--;
    ll ans = N*(1+N)/2;
    cout <<ans<< "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int INT_INF = 2147483647;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef pair<int,int> P;

int main(){
    string s;
    cin >> s;
    int n = s.size();
    vector<char> ans;
    rep(i,n)cout << 'x';
    cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll MOD = 1e9+7;
    typedef pair<int,int> P;
    #define INF 1e9
    #define rep(i,N) for(int i=0;i<N;i++)
     
    double ans = 0;
    double tmp = 0;
    double vM[1000005];
     
    int main(){
      ll n,k;
      cin>>n>>k;
      rep(i,n){
        double p;
        cin>>p;
        vM[i] = double(double((1 + p) * (p)) / 2);
        vM[i] /= p;
      }
     
      rep(i,n){
        tmp += vM[i];
        if( i < k ){
          ans = tmp;
        }else{
          tmp -= vM[i-k];
          if(tmp > ans){
            ans = tmp;
          }
        }
      }
      
      cout<<setprecision(10)<<ans<<endl;
     
    }

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

int main(){
    string s;
    cin >> s;
    if(s[2] == s[3] && s[4] == s[5]){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vii vector<pair<int, int> >
#define fi first
#define se second
#define int long long
const int mod = 1e9+7;
int dp[5005][5005];
int binpow(int a, int b)
{
	if(!b) return 1;
	int t=binpow(a, b/2);
	if(b&1) return t*t%mod*a%mod;
	return t*t%mod;
}
int inv(int x)
{
	return binpow(x, mod-2);
}
signed main()
{
	int n; string s;
	cin>>n>>s;
	dp[0][0]=1;
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=n; j++)
		{
			dp[i][j]+=dp[i-1][max(j - 1, 0ll)];
			dp[i][j]+=2*dp[i-1][j+1];
			dp[i][j]%=mod;
		}
	}
	int ans = dp[n][s.length()];
	cout<<ans; 
}


Measured memory_bytes: 199144
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int a,b;
	int has[3];
	for(int i=0;i<3;i++)
	has[i]=0;
	cin>>a;
	cin>>b;
	has[a-1]++;
	has[b-1]++;
	for(int i=0;i<3;i++)
	{
		if(has[i]==0)
		cout<<i+1;
	}
}
	

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef vector<llong> V;

#define _ cin.tie(0);ios::sync_with_stdio(false);
int a,b,c,d;
int main(){ _;
  cin>>a>>b>>c>>d;
  cout<<min(a,b)+min(c,d)<<endl;

  return 0;
}


Measured memory_bytes: 256
def inv(a):
    m=10**9+7
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m


def main():
    MOD=10**9+7
    n,k=map(int,input().split())
    a=list(map(int,input().split()))

    frac=[1]
    for i in range(1,n+1):
        frac.append(frac[-1]*i%MOD)
    
    fracinv=[inv(frac[i]) for i in range(n+1)]


    dp=[[0]*(n+1) for _ in range(k)]

    for x in range(a[0]+1):
        dp[0][x]=frac[n]*frac[n-x]*inv(frac[a[0]-x]*frac[n-a[0]]*frac[x])%MOD

    for i in range(k-1):
        ai=a[i+1]
        for j in range(n+1):
            for x in range(ai+1):
                p=j+x
                if p>n: break
                tmp=dp[i][j]
                tmp=tmp*frac[n-x]%MOD
                tmp=tmp*fracinv[ai-x]%MOD
                tmp=tmp*fracinv[n-ai]%MOD
                tmp=tmp*fracinv[x]%MOD
                dp[i+1][p]=(dp[i+1][p]+tmp)%MOD
    print(dp[k-1][n]%MOD)

if __name__ == "__main__":
    main()

Measured memory_bytes: 63836
#include<iostream>
#include<vector>
#include<cmath>
int main(){
	while(1){
		int a=0,b=0,c=0;
		std::cin>>a>>b>>c;
		if(a==0&&b==0&&c==0)break;
		int d=0;
		std::cin>>d;
		int p=0,q=0;
		if(a>b&&a>c){
			p=b*b+c*c;
		}else if(b>a&&b>c){
			p=a*a+c*c;
		}else if(c>a&&c>b){
			p=a*a+b*b;
		}
		q=sqrt(p);
		for(int i=0;i<d;i++){
			int n=0;
			std::cin>>n;
			if(2*n>q){
				std::cout<<"OK"<<std::endl;
			}else{
				std::cout<<"NA"<<std::endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1152
// Tazoe

#include <iostream>
using namespace std;

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

		if(n==0)
			break;

		char G[257][257];
		for(int i=0; i<=n+1; i++){
			for(int j=0; j<=n+1; j++){
				G[i][j] = '0';
			}
		}

		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				cin >> G[i][j];
			}
		}

		int DP_max = 0;

		int DP[257][257][4];
		for(int i=0; i<=n+1; i++){
			for(int j=0; j<=n+1; j++){
				for(int k=0; k<4; k++){
					DP[i][j][k] = 0;
				}
			}
		}

		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(G[i][j]=='0')
					continue;

				DP[i][j][0] = DP[i-1][j][0]+1;
				DP[i][j][1] = DP[i][j-1][1]+1;
				DP[i][j][2] = DP[i-1][j-1][2]+1;
				DP[i][j][3] = DP[i-1][j+1][3]+1;

				for(int k=0; k<4; k++){
					if(DP[i][j][k]>DP_max){
						DP_max = DP[i][j][k];
					}
				}
			}
		}

		cout << DP_max << '\n';
	}

	return 0;
}

Measured memory_bytes: 1956
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

int n;
int m;
int main(){
    cin >> n;
    m = n * (n - 1)/2 - n/2;
    cout << m << endl;
    for(int i = 1;i <= n;i++){
        for(int j = i + 1;j <= n;j++){
            if(i + j == (n % 2 ? n : n + 1))continue;
            cout << i << " " << j << endl;
        }
    }
}

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

int main() {
	int a, b, c;
	int x;
	cin >> a >> b >> c >> x;
	int s, t, u;
	int cnt = 0;
	for (s = a; s >= 0; s--)for (t = b; t >= 0; t--)for (u = c; u >= 0; u--)if ((500*s + 100*t + 50*u) == x)cnt++;
	cout << cnt << endl;
}

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

int main(){
  int A,B,C,D;
  int r,l;
  cin >> A >> B >> C >> D;
  l = A +B;
  r = C +D;

  if(r > l){
    cout << "Right" <<endl;
  }
  if(r== l){
    cout << "Balanced" <<endl;
  }
  if(r < l){
    cout << "Left" <<endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <set>
#include <stdio.h>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;

int main(void){
    int N;
    ll D, A;
    cin >> N >> D >> A;
    vector<pair<ll, ll> > XH(N);
    for(int i = 0; i < N; i++) {
        cin >> XH[i].first >> XH[i].second;
        XH[i].second = (XH[i].second + A - 1 ) / A;
    }
    
    sort(XH.begin(), XH.end());
  
    
    ll res = 0;
    ll num = 0;
    queue<pair<ll, ll> > que;
    for(int i = 0; i < N; i++){
        while(!que.empty() && que.front().first < XH[i].first) {
            num -= que.front().second;
            que.pop();
        }
        
        XH[i].second -= num;
        if(XH[i].second <= 0) continue;
        res += XH[i].second;
        que.push(make_pair(XH[i].first + 2*D, XH[i].second));
        num+=XH[i].second;
    }

    cout << res << endl;
}


Measured memory_bytes: 4992
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <string>
#include <climits>
using namespace std;

int lcs(string& x, string& y)
{
    int i, j, m = x.length(), n = y.length();
    vector<vector<int> > c(m + 1, vector<int>(n + 1));
    x.insert(x.begin(), ' ');
    y.insert(y.begin(), ' ');
    for (i = 1; i <= m; i++) c[i][0] = 0;
    for (j = 1; j <= n; j++) c[0][j] = 0;
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (x[i] == y[j])
                c[i][j] = c[i - 1][j - 1] + 1;
            else
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
        }
    }
    return c[m][n];
}

int main()
{
    int i, n;
    cin >> n;
    string x, y;
    for (i = 0; i < n; i++) {
        cin >> x >> y;
        cout << lcs(x, y) << endl;
    }
    return 0;
}

Measured memory_bytes: 6788
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

vector<long long> divisor(long long n) {
  vector<long long> d;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      d.push_back(i);
      if(i != n / i) d.push_back(n / i);
    }
  }
  sort(d.begin(), d.end());
  return d;
}

int main(){
  ll x;
  cin>>x;
  vector<ll>d=divisor(x);
  for(auto p:d){
    ll q=x/p;
    for(ll i=-1000;i<=1000;i++){
      ll t=(i+p)*(i+p)*(i+p)*(i+p)+(i+p)*(i+p)*(i+p)*i+(i+p)*(i+p)*i*i+(i+p)*i*i*i+i*i*i*i;
      if(t==q){
        cout<<i+p<<' '<<i<<endl;
        return(0);
      }
    }
  }
  return(0);
}


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

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

int main(){
	int a=get(),b=get(),c=get();
	int ans=0;
	if (c<=a+b)ans=(LL)c+b;
	else ans=(LL)a+b+b+1;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import sys
write = sys.stdout.write

def chooseop(a, b, cmd):
    if cmd == 0:
        return a+b
    elif cmd == 1:
        return a-b

def calc(nums, ops):
    ans = nums[0]
    for i in range(1, 4):
        ans = chooseop(ans, nums[i], ops[i-1])
    return ans

def printresult(n, ops):
    op = ["+", "-", "*", "/"]
    write(n[0] + op[ops[0]] + n[1] + op[ops[1]] + n[2] + op[ops[2]] + n[3] + "=7\n")

n = input()
nums = []
if len(n) != 4:
    write("error\n")
    sys.exit()
for i in range(4):
    nums.append(int(n[i]))

zenbu = 2**3
for i in range(zenbu):
    ops = []
    bit = i
    for j in range(3):
        ops.append(bit % 2)
        bit //= 2
    res = calc(nums, ops)
    if res == 7:
        printresult(n, ops)
        break

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct data
{
	int x,y;
};
set<data> s;
set<int> ss[N];
int n,fa[N],x,y;
bool operator <(data a,data b)
{
	if(a.x!=b.x)
	{
		return a.x<b.x;
	}
	return a.y<b.y;
}
int findfa(int x)
{
	if(fa[x]==x)
	{
		return x;
	}
	return fa[x]=findfa(fa[x]);
}
void adde(int x,int y)
{
	set<int>::iterator it=ss[x].find(y);
	if(it==ss[x].end())
	{
		ss[x].insert(y);
	}else{
		ss[x].erase(y);
		if(x>y)
		{
			swap(x,y);
		}
		s.insert((data){
			x,y
		});
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		adde(x,y);
		adde(y,x);
	}
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		adde(x,y);
		adde(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	while(!s.empty())
	{
		set<data>::iterator it=s.begin();
		set<int>::iterator its;
		int x=findfa((*it).x),y=findfa((*it).y);
		s.erase(it);
		if(ss[x].size()>ss[y].size())
		{
			swap(x,y);
		}
		fa[x]=y;
		for(its=ss[x].begin();its!=ss[x].end();its++)
		{
			ss[*its].erase(x);
			adde(*its,y);
			adde(y,*its);
		}
		ss[x].clear();
		n--;
	}
	if(n==1)
	{
		puts("YES");
	}else{
		puts("NO");
	}
	return 0;
}

Measured memory_bytes: 24064
a11, a12, a13 = list(map(int, input().split()))
a21, a22, a23 = list(map(int, input().split()))
a31, a32, a33 = list(map(int, input().split()))
n = int(input())
b = [0]*n
for i in range(n):
  b[i] = int(input())
  if a11 == b[i]:
    a11 = -1
  if a12 == b[i]:
    a12 = -1
  if a13 == b[i]:
    a13 = -1
  if a21 == b[i]:
    a21 = -1
  if a22 == b[i]:
    a22 = -1
  if a23 == b[i]:
    a23 = -1
  if a31 == b[i]:
    a31 = -1
  if a32 == b[i]:
    a32 = -1
  if a33 == b[i]:
    a33 = -1
flag = False
if a11 == -1 and a12 == -1 and a13 ==-1:
  flag = True
if a21 == -1 and a22 == -1 and a23 ==-1:
  flag = True
if a31 == -1 and a32 == -1 and a33 ==-1:
  flag = True
if a11 == -1 and a21 == -1 and a31 ==-1:
  flag = True
if a12 == -1 and a22 == -1 and a32 ==-1:
  flag = True
if a13 == -1 and a23 == -1 and a33 ==-1:
  flag = True
if a11 == -1 and a22 == -1 and a33 ==-1:
  flag = True
if a13 == -1 and a22 == -1 and a31 ==-1:
  flag = True
if flag:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
n = int(input())
if n < 10:
    print(n)
elif n < 100:
    print(9)
elif n < 1000:
    print(9+(n-99))
elif n < 10000:
    print(909)
elif n < 100000:
    print(909+(n-9999))
elif n == 100000:
    print(90909)


Measured memory_bytes: 2940
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
typedef long long ll;
int main(){
	int n;
	cin >> n;
	ll x=1,y=1;
	ll l,r;
	rep(i,n){
		cin >> l>> r;
		ll rx = (x+l-1)/l;
		ll ry = (y+r-1)/r;
		ll mi = max(rx, ry);
		x=l*mi;
		y=r*mi;
	}
	cout << x + y << endl;
}
		


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

int main() {
  int a,b,c,d;
  cin >> a>>b>>c>>d;
  cout<<(a-c)*(b-d)<<endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

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

		while (true) {
			String input = sc.next();
			if("-".equals(input)){
				break;
			}
			
			final int m = sc.nextInt();

			for (int i = 0; i < m; i++) {
				final int h = sc.nextInt();
				
				input = input.substring(h) + input.substring(0, h);
			}
			
			System.out.println(input);
		}
	}
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n;
  cin >> n;
  string s = to_string(n);

  if ((s[0] > s[1])||((s[0] == s[1])&&(s[1] >= s[2]))) {
    cout << s[0] << s[0] << s[0] << "\n";
  } else {
    int a = (n / 100) + 1;
    cout << a << a << a << "\n";
  }
  return 0;
}


Measured memory_bytes: 256
uses math;
var
  a:array[1..2000] of longint;
  n,x,i:longint;
begin
  readln(n,x,x);
  for i:=1 to n do read(a[i]);
  if n=1 then writeln(abs(a[1]-x)) else writeln(max(abs(a[n]-a[n-1]),abs(a[n]-x)));
end.

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <functional>
#include <bitset>
#include <utility>
#include <sstream>
#include <fstream>
#include <stack>
#include <cstdlib>
#include <complex>
#include <set>

using namespace std;

#define INF 1070000000LL
#define pb push_back
#define irep(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) irep(i,0,n)

typedef long long lint;
typedef pair<int, int> pint;
struct Edge{
    int to,weight;
};
typedef vector<vector<Edge> > Graph;


int main(){
    int a,b;
    cin >> a >> b;
    if(b == 1){
	cout << 0 << endl;
	return 0;
    }
    b -= a;
    int ans = 1;
    while(1){
	if(b > 0){
	    b -= (a-1);
	    ++ans;
	}
	else break;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define fi first
#define se second
#define pii pair<long long,long long>
#define int long long
#define endl '\n'
#define pll pair<long long,long long>
#define LONGLONG_MAX 100000000000000
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
long long power(long long a,long long b){
    long long ans=1;
    while(b>0){
        if(b&1){ans=(ans*a);}
                a=(a*a);
                b>>=1;
        }
    return ans;
        
}
set<pii>s;
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    srand(time(0));
    int n,k,c;
    cin>>n>>k>>c;
    string s;
    cin>>s;
    int a[n]={0};
    int pre[n+1]={0};
    int x=0;
    int d[n]={0};
    for(int i=n-1;i>=0;i--){
        if(s[i]=='o'){
            if(i+c+1>n)a[i]=1;
            else a[i]=pre[i+c+1]+1;
        }
        pre[i]=max(pre[i+1],a[i]);
        d[i]=a[i];
        d[i]=min(d[i],k);
    }
    vector<int>v[n+n];
    int b[n+n]={0};
    for(int i=0;i<n;i++){
        b[i]=n;
    }
    x=k;
    for(int i=0;i<n;i++){
        x=min(x,b[i]);
        //cout<<x<<" ";
        if(d[i]>=x){
            if(x==a[i])
            v[d[i]].push_back(i);
            b[i+c+1]=min(b[i+c+1],min(x,a[i])-1);
        }
    }
    set<int>ans;
    for(int i=1;i<=k;i++){
        if(v[i].size()==1)ans.insert(v[i][0]);
    }
    for(auto i:ans)cout<<i+1<<endl;
    return 0;

}


Measured memory_bytes: 34580
//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=nxt[i])
#define repvc(i,vc) for(int i=0,Sz=vc.size();i<Sz;++i)
using namespace std;
inline int read()
{
	char ch=getchar();int ret=0,f=1;
	while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	for(;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret*f;
}

inline void print(string name,int *arr,int len){
	rep(i,1,len) printf("%s[%d]=%d\n",name.c_str(),i,arr[i]);puts("");
}
inline void print(string name,int a){
	printf("%s=%d\n",name.c_str(),a);puts("");
}

typedef long long ll;
const int INF=1<<30;

const int maxn=200000+10;

int a[maxn],ans[maxn];
int main()
{
	int n;cin>>n;
	rep(i,1,n) a[i]=read();
	int cnt=0;
	for(int i=n;i>=1;--i)
	{
		int sum=0;
		for(int j=i;j<=n;j+=i) sum^=ans[j];
		if(sum==a[i]) ans[i]=0;
		else {ans[i]=1;++cnt;}
	}
	cout<<cnt<<endl;
	rep(i,1,n) if(ans[i]) printf("%d ",i);
	return 0;
}


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

int main(){
	int h,n,i,dam = 0;
	cin >> h;
	cin >> n;
	int a[n];
	for(i = 0; i < n; i++){
		cin >> a[i];
	}
	for(i = 0; i < n; i++){
		dam = dam + a[i];
	}
	if(dam >= h){
		cout << "Yes";
	}
	else{
		cout << "No";
	}

	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

struct store
{
	int point, count;
};

bool pred(const store& l, const store& r)
{
	return l.point < r.point;
}

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

	vector<store> stores(N);

	for (int i = 0; i < N; i++)
	{
		store A;
		cin >> A.point >> A.count;

		stores[i] = A;
	}

	sort(stores.begin(), stores.end(), pred);

	long long ans = 0;
	int index = 0;
	for (int i = 0; i < M; i++)
	{
		if (stores[index].count > 0)
		{
			ans += stores[index].point;
			stores[index].count--;
		}
		else
		{
			index++;
			i--;
		}
	}

	cout << ans << endl;

	return 0;
}


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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

int main(void) {
    int n, m;
    cin >> n >> m;

    vector<bool> fst(n, false);
    vector<bool> snd(n, false);
    int a, b;
    for(int im=0;im<m;im++) {
        cin >> a >> b; a--; b--;
        if(a==0) fst.at(b) = true;
        if(b==n-1) snd.at(a) = true;
    }

    queue<int> q; 
    for(int in=0;in<n;in++) {
        if(fst.at(in)==true) q.push(in);
    }

    int v;
    while(!q.empty()) {
        v = q.front(); q.pop();
        if(snd.at(v)==true) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}


Measured memory_bytes: 768