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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))

typedef long long ll;

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

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

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

ll powmod(ll a,ll b){ll c=1; while(b>0){ if(b&1){ c=a*c%mod; } a=a*a%mod; b>>=1; } return c;}
ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

int main()
{
	ll X;cin>>X;
    ll ans=100;
    ll tosi=0;
    while(ans<X){
        ans*=1.01;
        tosi++;
    }
    cout<<tosi<<endl;
}

 
    
        






Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

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

int main(){
    int n, m;
    cin >> n;
    map<int, int> d;
    rep(i, n){
        int x;
        cin >> x;
        d[x]++;
    }
    cin >> m;
    vector<int> t;
    rep(i, n) {
      int x;
      cin >> x;
      t.push_back(x);
    }
    string ans = "YES";
    rep(i, m){
        if(d[t[i]]==0){
            ans = "NO";
            break;
        }
        d[t[i]]--;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 13700
import math

#input
n = int(input())

def main():
    cnt = 0
    for a in range(1, n):
        if a < n/a:
            m = int(n/a)
            for b in range(a,m+2):
                if a * b < n :
                    if a == b :
                        cnt += 1
                    else :
                        cnt += 2
    print(cnt)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9108
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll N, K; cin >> N >> K;
    vector<ll> v;
    rep(i, N) {
        ll num; cin >> num;
        v.push_back(num);
    }

    ll maxn = -inf;
    for (ll x = 0; x <= min(N, K); x++) {
        // x: sum of a and b;
        priority_queue<ll, vector<ll>, greater<ll>> pque;
        for (ll a = 0; a <= x; a++) {
            deque<ll> que(v.begin(), v.end());
            ll b = x - a;
            rep(i, a) {
                ll num = que.front(); que.pop_front();
                pque.push(num);
            }

            rep(i, b) {
                ll num = que.back(); que.pop_back();
                pque.push(num);
            }

            rep(i, K - x) {
                if (pque.size() && pque.top() <= 0) pque.pop();
            }

            ll total = 0;
            while (pque.size()) {
                total += pque.top(); pque.pop();
            }
            maxn = max(maxn, total);
        }
    }
    cout << maxn << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<map>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<list>
#include<string>
#include<climits>
#define ll long long 
#define inf 0x7f7f7f7f
#define io ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
typedef pair<int,int> p;
int main()
{
	int n,m;
	cin>>n>>m;
	int x=max(n,m),y=min(n,m);
	for(int i=0;i<x;i++)
	cout<<y;
}

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

using namespace std;

int main() {
  int A, B, C, ans = -0x7fffffff;
  
  cin >> A >> B >> C;
  
  ans = max(ans, A * 10 + B + C);
  ans = max(ans, B * 10 + C + A);
  ans = max(ans, C * 10 + B + A);
  
  cout << ans << endl;
  
  return 0;
}

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

int main(){
    int n; cin >> n;
    vector<long long> height(n+1);
    map<int,long long> h_ind;
    map<int,long long> h__ind;
    long long ans = 0;
    for(int i=1;i<=n;++i){
        cin >> height[i];
        if(h_ind.count(-1*height[i]+i)) h_ind[-1*height[i]+i]+=1;
        else h_ind[-1*height[i]+i]=1;
        if(h__ind.count(height[i]+i)) h__ind[height[i]+i]+=1;
        else h__ind[height[i]+i]=1;
    }
    for(auto e:h_ind){
        ans += e.second*h__ind[e.first];
    }
    cout << ans << endl;
}

Measured memory_bytes: 38960
#include<bits/stdc++.h>
using namespace std;
#define file "harem"
typedef long long ll;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define getchar gc//最后要修改，不修改会导致读入速度降低
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
const int maxn=10000002;
int ans[maxn];
struct query{
	int l,r;
	bool operator <(const query& rhs)const{
		return r-l<rhs.r-rhs.l;
	}
}q[maxn],w[maxn];
int sum[300002];
struct bit{
	int n;
	int a[300002];
	void add(int p,int v){
		for(;p<=n;p+=p&-p)
			a[p]+=v;
	}
	int query(int p){
		int ans=0;
		for(;p;p-=p&-p)
			ans+=a[p];
		return ans;
	}
}b;
int main(){
	//freopen(file".in","r",stdin);
	//freopen(file".out","w",stdout);
	int m=read(),n=read();
	if (m<=10000){
		while(m--){
			int l=read()-1,r=read();
			int nxt;
			for(int i=1;i<=l;i=nxt+1){
				nxt=min(l/(l/i),r/(r/i));
				if (l/i!=r/i)
					ans[i]++,ans[nxt+1]--;
			}
			//(l,r]
			ans[l+1]++,ans[r+1]--;
		}
		//ll qwq=0;
		for(int i=1;i<=n;i++){
			ans[i]+=ans[i-1];
			printf("%d\n",ans[i]);
		}
		//printf("%lld",qwq);
		return 0;
	}
	for(int i=1;i<=m;i++){
		w[i].l=read(),w[i].r=read();
		sum[w[i].r-w[i].l]++;
	}
	for(int i=1;i<=n;i++)
		sum[i]+=sum[i-1];
	for(int i=1;i<=m;i++)
		q[sum[w[i].r-w[i].l]--]=w[i];
	b.n=n;
	int j=1;
	for(int i=1;i<=n;i++){
		while(j<=m && q[j].r-q[j].l<i){
			b.add(q[j].l,1);
			b.add(q[j].r+1,-1);
			j++;
		}
		int now=m-j+1;
		for(int j=i;j<=n;j+=i)
			now+=b.query(j);
		printf("%d\n",now);
	}
}


Measured memory_bytes: 9984
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
c=0
for j in range(n-1,-1,-1):
  if (c+l[j][0])%l[j][1]!=0:c+=l[j][1]-((c+l[j][0])%l[j][1])
print(c)

Measured memory_bytes: 27380
#include <iostream>
int main(){
	while (true){
		int input_num[2], sum;
		int count = 0;
		std::cin >> input_num[0] >> input_num[1];
		if (std::cin.eof())
			break;
		sum = input_num[0] + input_num[1];
		while (sum){
			count++;
			sum /= 10;
		}
		std::cout << count << '\n';
	}
}


Measured memory_bytes: 3092
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = (dp[i-1]|(dp[i-1]<<ls[i-1]))&((1<<k)-1)
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1:],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)


Measured memory_bytes: 7028
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define loop(n) for(int i=0; i<n; i++)
void solve()
{
	int x;cin>>x;
	int n=100;
	int count=0;
	while(n<x)
	{
	    n*=1.01;
	    count++;
	}
	cout<<count;
	return;
}
int32_t main() 
{ 
	fast;
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0; 
}

Measured memory_bytes: 3648
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<ctime>
#include<vector>
#include<bitset>
#include<string>
#include<cstdio>
#include<numeric>
#include<utility>
#include<sstream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<unordered_map>
#define _USE_MATH_DEFINES
#define inf 999999999999999999
#define rep(i,n,m) for(lli i=(lli)(n);i<(lli)(m);++i)
#define reep(i,n,m) for(int i=(int)(n);i<=(int)(m);++i)
#define per(i,m,n) for(lli i=(int)(m)-1;i>=(int)(n);--i)
#define st(n) sort(n.begin(), n.end())
#define rev(n) reverse(n.begin(),n.end())
#define ou(S) cout << S << endl
#define pb(n) push_back(n)
#define ue(N) N.erase(unique(N.begin(),N.end()),N.end());
#define nou(S) cout << S
#define hou(S) cout << setprecision(30) << S << endl
#define vec(K,L,N,S) vector<L> K(N,S)
#define dv(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define tv(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define maxx 5100000
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define endl "\n"
typedef long long int lli;
typedef unsigned long long int uli;
const uli mod = 1e9 + 7;
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);


	int x;
	cin >> x;
	if(x >= 400 && x < 600)
		cout << 8 << endl;
	if(x >= 600 && x < 800)
		cout << 7 << endl;
	if(x >= 800 && x < 1000)
		cout << 6 << endl;
	if(x >= 1000 && x < 1200)
		cout << 5 << endl;
	if(x >= 1200 && x < 1400)
		cout << 4 << endl;
	if(x >= 1400 && x < 1600)
		cout << 3 << endl;
	if(x >= 1600 && x < 1800)
		cout << 2 << endl;
	if(x >= 1800 && x < 2000)
		cout << 1 << endl;
}

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

int main (){
    ll n,ans=0;
    cin>>n;
    for(ll i=1;i<=n;i++){
        string s=to_string(i);
        if(s.size()%2==1)   ans++;
    }
    cout<<ans;
    return 0;
}





Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	int n, i, money, amari;
	
	scanf("%d",&n);
	
	money = 100000;
	
	for(i = 0; i < n; i++ ) {
		money *= 1.05;
		if ( money % 1000 ){
			amari = money % 1000;
			money = money - amari + 1000;
		}
	}
	printf("%d\n",money);
	return(0);
}

Measured memory_bytes: 592
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;
const int mod=1000000007;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
int dyy[]={0,-1,0,1};
int dxx[]={-1,0,1,0};

/*#define int ll*/
signed main(){
    int n;
    cin>>n;
    ll a[1001];
    rep(i,0,1001)a[i]=0;
    rep(i,2,n+1){
        ll h=i;
        rep(j,2,i+1){
            
            while(h%j==0){
                a[j]++;
                h/=j;
            }
        }
    }
    ll ans=1;
    rep(i,0,1000)if(a[i]>0)ans*=(a[i]+1),ans%=mod;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=[]
    for i in range(N):
        X,L=map(int,input().split())

        A.append([X-L,X+L])

    A=sorted(A, key=lambda x: x[1])
    cur=-(10**10)
    cnt=0
    for i in range(N):
        if A[i][0]<cur: continue
        else:
            cur=A[i][1]
            cnt+=1
    print(cnt)



    
    

    
resolve()

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int a, b, c;
  cin >> a >> b >> c;
  
  int ans = 0;
  for (int i = a; i <= b; i++) {
    if (c % i == 0) ans++;
  }
  
  cout << ans << '\n';
}


Measured memory_bytes: 3216
#! /usr/bin/ruby

min = 1.0 / 0
max = -min
sum = 0
n = $stdin.gets.to_i
$stdin.gets.split(/\s+/).map(&:to_i).each do |x|
	min = x if x < min
	max = x if max < x
	sum += x
end
printf "%d %d %d\n", min, max, sum

Measured memory_bytes: 9096
#include<cstdio>
#include<map>
#include<queue>
using namespace std;
const int dir[4]={-4,1,4,-1};
struct state
{
	int board[8];
	bool operator < (const state &t)const
	{
		for(int i=0;i<8;i++)
			if(board[i]!=t.board[i])
				return board[i]<t.board[i];
		return 0;
	}
	bool operator != (const state &t)const
	{
		for(int i=0;i<8;i++)
			if(board[i]!=t.board[i])
				return 1;
		return 0;
	}
};
map<state,int>step;
queue<state>Q;
void BFS()
{
	state st={{0,1,2,3,4,5,6,7}},t,tt;
	int pos,tpos;
	Q.push(st);
	while(!Q.empty())
	{
		t=Q.front();
		Q.pop();
		for(pos=0;pos<8&&t.board[pos]!=0;pos++);
		for(int d=0;d<4;d++)
		{
			tpos=pos+dir[d];
			if(tpos<0||tpos>=8)continue;
			if(d==1&&pos==3)continue;
			if(d==3&&pos==4)continue;
			tt=t;
			swap(tt.board[pos],tt.board[tpos]);
			if(tt!=st&&step[tt]==0)
			{
				step[tt]=step[t]+1;
				Q.push(tt);
			}
		}
	}
}
int main()
{
	BFS();
	state tmp;
	while(~scanf("%d",tmp.board))
	{
		for(int i=1;i<8;i++)
			scanf("%d",tmp.board+i);
		printf("%d\n",step[tmp]);
	}
	return 0;
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

const int INF = 1<<28;

struct edge {int to;int cost;int time;};

const int M_N=100;

int d[M_N+1][30];
int N,M,H,K;

struct Dijkstra{

    void dijkstra(int s,vector<vector<edge>> G){
        priority_queue<pair<P,int>,vector<pair<P,int>>,greater<pair<P,int>>> que;
        que.push(make_pair(make_pair(0,0),s));
        d[s][0]=0;
        while(!que.empty()){
            pair<P,int> p=que.top();
            que.pop();
            int v=p.second;
            int c=p.first.first;
            int h=p.first.second;
            if(d[v][h]<c) continue;
            for(int i=0;i<G[v].size();i++){
                edge e=G[v][i];
                if(h+e.time>H) continue;
                if(d[e.to][h+e.time]>d[v][h]+e.cost){
                    d[e.to][h+e.time]=d[v][h]+e.cost;
                    que.push(make_pair(make_pair(d[e.to][h+e.time],h+e.time),e.to));
                }
            }
        }
    }

};


int main(){
    while(cin >> N >> M >> H >> K,N){
        vector<int> a(M),b(M),c(M),h(M),r(M);
        for (int i = 0; i < M; i++) {
            cin >> a[i] >> b[i] >> c[i] >> h[i] >> r[i];
            a[i]--,b[i]--,r[i]--;
        }
        int s,t;cin >> s >> t;
        s--,t--;
        int p;cin >> p;
        vector<P> k(p);
        for (int i = 0; i < p; i++) {
            int l,dd;cin >> l >> dd;
            int x=0;
            for (int j = 0; j < l; j++) {
                int y;cin >> y;
                y--;
                x|=(1<<y);
            }
            k[i]=make_pair(dd,x);
        }
        vector<int> dp(1<<K,INF);
        dp[0]=0;
        for (int bit = 0; bit < 1<<K; bit++) {
            for (int i = 0; i < p; i++) {
                int nx = bit;
                nx |= k[i].second;
                dp[nx] = min(dp[nx],dp[bit]+k[i].first);
            }
        }
        int ans = INF;
        for (int bit = 0; bit < 1<<K; bit++) {
            vector<vector<edge>> G(N+1);
            for (int i = 0; i < M; i++) {
                if(bit&(1<<r[i])){
                    G[a[i]].push_back({b[i],0,h[i]});
                    G[b[i]].push_back({a[i],0,h[i]});
                }
                else{
                    G[a[i]].push_back({b[i],c[i],h[i]});
                    G[b[i]].push_back({a[i],c[i],h[i]});
                }
            }
            for (int i = 0; i < 101; i++) {
                for (int j = 0; j < 30; j++) {
                    d[i][j]=INF;
                }
            }
            Dijkstra ds;
            ds.dijkstra(s,G);
            int sum = INF;
            for (int i = 0; i <= H; i++) {
                sum = min(d[t][i],sum);
            }
            ans=min(ans,sum+dp[bit]);
        }
        if(ans==INF) cout << -1 << endl;
        else cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3224
# coding: utf-8

import sys

N = int(input())
t = [0]
x = [0]
y = [0]
for i in range(N):
	txy = [int(x) for x in input().split()]
	t.append(txy[0])
	x.append(txy[1])
	y.append(txy[2])

for i in range(N):
	d = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i])
	dt = t[i + 1] - t[i]
	if dt < d or dt % 2 != d % 2:
		print("No")
		sys.exit()
	
print("Yes")

Measured memory_bytes: 11816
package main

import "fmt"

func main() {
	var H, W, h, w, all_cell, ans int
	fmt.Scanf("%d %d\n", &H, &W)
	fmt.Scanf("%d %d", &h, &w)
	all_cell = H * W
	ans = all_cell - (h*W + w*H - (h * w))
	fmt.Println(ans)
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int num, times;
    cin >> num >> times;
    
    queue< pair<string, int> >Queue;
    string name;
    int t;
    for(int i=0; i<num; ++i) {
        cin >> name;
        cin >> t;
        Queue.push(make_pair(name, t));
    }

    int elapsed = 0;
    while(Queue.size() != 0) {
        auto process = Queue.front();
        Queue.pop();
        
        if(process.second - times <= 0) {
            elapsed += process.second;
            cout << process.first << " " << elapsed << endl;
        } else {
            elapsed += times;
            Queue.push(make_pair(process.first, process.second - times));
        }
    }
}



Measured memory_bytes: 6284
from sys import stdin,stdout
LI=lambda:list(map(int,input().split()))
MAP=lambda:map(int,input().split())
IN=lambda:int(input())
S=lambda:input()
import math
def p(a):print(" ".join(list(map(str,a))))
from collections import Counter

n,k=MAP()
a=sorted(LI())
print(sum(a[:k]))



Measured memory_bytes: 9508
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t,n,i,j=0,c=0;
  cin>>t;
  for(i=0;i<t;i++)
  {
     cin>>n;
     if(n>=c)
     {
         c=n;
         j++;
     }
  }
 cout<<j<<"\n";


return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define ld long double
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpii vector<pii>
#define gr vector<vpii>
#define str string
#define mask vector<bool>
#define vs vector<str>
#define pq priority_queue
#define ordered_set_of(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
#define fi first
#define se second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define nub(x) x.resize(unique(all(x)) - x.begin())
#define TWO class T1, class T2
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define EPS 1E-14
#define GAME_OVER return 0
using namespace std;
using namespace __gnu_pbds;
char _$ = ' ';
struct sep {sep(char c) {_$ = c;}};
ostream& operator<<(ostream& o, sep s) {return o;}
template<TWO> ostream& operator<<(ostream& o, pair<T1, T2> x) {return o << x.fi << ' ' << x.se;}
template<TWO> istream& operator>>(istream& i, pair<T1, T2>& x) {return i >> x.fi >> x.se;}
template<class T> ostream& operator<<(ostream& o, vector<T> x) {for (auto it : x) o << it << _$; return o;}
template<class T> istream& operator>>(istream& i, vector<T>& x) {for (auto& it : x) i >> it; return i;}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vvi g(n, vi());
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v), g[v].push_back(u);
    }
    vi d(n, LLONG_MAX), p(n, -1);
    d[0] = 0;
    queue<int> q;
    q.push(0);
    while (sz(q))
    {
        int v = q.front();
        q.pop();
        for (int to : g[v])
            if (d[to] > d[v] + 1)
            {
                d[to] = d[v] + 1;
                if (p[to] != -1)
                {
                    cout << "No" << endl;
                    GAME_OVER; 
                }
                p[to] = v;
                q.push(to);
            }
    }
    cout << "Yes" << endl;
    for (int i = 1; i < n; i++)
        cout << p[i] + 1 << endl;
    GAME_OVER;
}

Measured memory_bytes: 13736
a, b = map(int, input().split())
nega_num = 0
posi_num = 0
if a < 0 and b < 0:
    nega_num = b - a + 1
elif a < 0 and b >= 0:
    print('Zero')
    exit()
elif a == 0:
    print('Zero')
    exit()
elif a > 0:
    print('Positive')
    exit()
if nega_num % 2 == 1:
    print('Negative')
else:
    print('Positive')

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

int main(){
	int a,b,k;
	cin >> a >> b >> k;
	if(2*k<b-a+1){
		for(int i=0;i<k;++i)cout << a+i << endl;
		for(int i=k-1;i>=0;--i)cout << b-i << endl;
	}else{
		for(int i=a;i<=b;++i)cout << i << endl;
	}
	return 0;
}

Measured memory_bytes: 256
from itertools import product
from copy import deepcopy, copy
class QueenMAP():
    __slots__ = ["yoko", "tate", "naname1", "naname2", "MAP"]
    def __init__(self):
        self.yoko = set()
        self.tate = set()
        self.naname1 = set()
        self.naname2 = set()
        self.MAP = [["."] * 8 for _ in range(8)]
    def add(self, y, x):
        self.MAP[y][x] = "Q"
        self.yoko.add(y)
        self.tate.add(x)
        self.naname1.add(y - x)
        self.naname2.add(x + y)
    def check(self, y, x):
        if y in self.yoko or x in self.tate or (y - x) in self.naname1 or (x + y) in self.naname2:
            return False
        return True
    def allcheck(self):
        for i in range(8):
            if not "Q" in self.MAP[i]:
                return False
        return True
def MAIN():
    f = lambda M: "\n".join("".join(map(str, m)) for m in M)
    QM = QueenMAP()
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        QM.add(a, b)
    dp = [(deepcopy(QM), n)]
    while dp:
        Q, cnt = dp.pop()
        if cnt == 8:
            if Q.allcheck():
                print(f(Q.MAP))
                break
            continue
        cnt += 1
        for i in range(8):
            for j in range(8):
                if Q.check(i, j):
                    CQ = deepcopy(Q)
                    CQ.add(i, j)
                    dp.append((CQ, cnt))
MAIN()



Measured memory_bytes: 6348
import sys

N, Y = map(int, input().split())
for i in range(N + 1):
    for j in range(N - i + 1):
        if 10000 * i + 5000 * j + 1000 * (N - i - j) == Y:
            print(i, j, N - i - j)
            sys.exit()
else:
    print(-1, -1, -1)


Measured memory_bytes: 3064
# -*- coding: utf-8 -*-

if __name__ == "__main__":
    n = int(input())

    flag = 0
    t, x, y = 0, 0, 0
    for i in range(n):
        newt, newx, newy = map(int, input().split())

        dift, difx, dify = newt - t, abs(newx - x), abs(newy - y)

        val = difx + dify
        if val > dift:
            flag = 1
            print("No")
            break
        if val % 2 != dift % 2:
            flag = 1
            print("No")
            break

        t, x, y = newt, newx, newy

    if flag == 0:
        print("Yes")


Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        if (N == 3 || N == 5 || N == 7)
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
}


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

int main()
{
	vector<int> RGB(3);
	int N;
	cin >> RGB[0] >> RGB[1] >> RGB[2] >> N;
	sort(RGB.begin(), RGB.end(),greater<int>());

	int max0 = N / RGB[0];
	int max1 = 0;
	int temp = 0;
	int result = 0;
	for (int r = 0; r <= max0; ++r) {
		temp = N - r * RGB[0];
		max1 = temp / RGB[1];
		for (int g = 0; g <= max1; ++g) {
			if ((temp - g * RGB[1]) % RGB[2] == 0) {
				++result;
			}
		}
	}

	cout << result << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=5005,INF=1<<30;

ll dp[MAX][MAX];

ll rui(ll a,ll b){
    ll ans=1;
    while(b>0){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}

ll sum[MAX];
ll naname[MAX][MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N,A,B;cin>>N>>A>>B;
    if(A>B) swap(A,B);
    if(A==1){
        cout<<rui(2,N)<<endl;
        return 0;
    }
    dp[0][0]=1;
    sum[0]=1;
    naname[0][0]=1;
    
    for(int i=1;i<=N;i++){
        for(int j=0;j<B;j++){
            if(j) dp[i][j]+=dp[i-1][j-1];
            
            if(j==1){
                //dp[i][j]+=(mod+sum[max(0,i-2)]-sum[max(0,i-A)]);
                //dp[i][j]%=mod;
                
                if(i-2>=0) dp[i][j]+=sum[i-2];
                if(i-(A+1)>=0) dp[i][j]+=mod-sum[i-(A+1)];
                dp[i][j]%=mod;
                /*for(int k=2;k<=A;k++){
                    for(int l=0;l<=B-1;l++){
                        if(i-k>=0) dp[i][j]+=dp[i-k][l];
                        dp[i][j]%=mod;
                    }
                }*/
            }
            
            if(i-(A+1)>=0&&j-(A+1)>=0) dp[i][j]+=naname[i-(A+1)][j-(A+1)];
            dp[i][j]%=mod;
            //dp[i][j]+=mod-naname[max(0,i-(A+1))][max(0,j-(A+1))]-naname[max(0,i-N)][max(0,j-N)];
            //dp[i][j]%=mod;
            
            /*for(int k=A+1;k<=N;k++){
                if(i-k>=0&&j-k>=0) dp[i][j]+=dp[i-k][j-k];
                dp[i][j]%=mod;
            }*/
        }
        
        ll S=0;
        for(int l=0;l<=B-1;l++){
            S+=dp[i][l];
            //S%=mod;
            if(S>=mod) S-=mod;
        }
        sum[i]=sum[i-1]+S;
        //sum[i]%=mod;
        if(sum[i]>=mod) sum[i]-=mod;
        
        naname[i][0]=dp[i][0];
        for(int j=1;j<=N;j++){
            naname[i][j]=naname[i-1][j-1]+dp[i][j];
            //naname[i][j]%=mod;
            if(naname[i][j]>=mod) naname[i][j]-=mod;
        }
    }
    
    ll ans=0;
    
    for(int i=1;i<N;i++){
        for(int j=1;j<B;j++){
            if(N-i<A||j+N-i<B){
                ans+=dp[i][j];
                //ans%=mod;
                if(ans>=mod) ans-=mod;
            }
        }
    }
    
    for(int j=0;j<B;j++){
        ans+=dp[N][j];
        ans%=mod;
    }
    
    cout<<(mod+rui(2,N)-ans)%mod<<endl;
}


Measured memory_bytes: 394700
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
int a[100];
int main()
{
    int p,q,r;
    scanf("%d%d%d",&p,&q,&r);
    a[1]=p+q;
    a[2]=r+q;
    a[3]=p+r;
    a[4]=q+r;
    a[5]=p+q;
    a[6]=p+r;
    sort(a+1,a+7);
    printf("%d\n",a[1]);

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String args[]){
		new Main().mainrun();
	}

	private Scanner scan;
	private int D,L,Ans = 0;

	private void mainrun() {
		scan = new Scanner(System.in);

		D = scan.nextInt();
		L = scan.nextInt();

		Ans += D / L + (D % L);

		System.out.println(Ans);

		scan.close();
	}

}


Measured memory_bytes: 26340
#include<bits/stdc++.h>
using namespace std;
#define rp(i,n) for(int i=0;i<n;i++)
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define lrp(i,n) for(long long i=0;i<n;i++)
#define lrep(i,m,n) for(long long i=m;i<=n;i++)
#define ll long long
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define abs(a,b) (a-b>0?a-b:b-a)


int main(){
    string s,t;
    cin  >> s >> t;
    if(s.size()!=t.size()){
        cout << "No" << endl;
    }else{
        rp(i,s.size()){
            vector<char> u(s.size());
            rp(j,u.size()){
                if(i+j<s.size()){
                    u.at(j)=s.at(i+j);
                }else{
                    u.at(j)=s.at(i+j-s.size());
                }
            }
            int cnt=0;
            rp(j,t.size()){
                if(t.at(j)==u.at(j)){
                    cnt++;
                }
            }
            if(cnt==t.size()){
                cout << "Yes" << endl;
                goto Exit;
            }
        }
        cout << "No" << endl;
    }
    
Exit:
    ;
}








Measured memory_bytes: 256
use std::io;

fn solve(s: &Vec<i32>) -> i32 {
    let mut dp = Vec::new();
    let m = s.iter().sum();
    dp.resize(m as usize + 1, 0);
    dp[0] = 1;
    for v in s {
        for i in (0..m).rev() {
            if dp[i as usize] != 0 {
                dp[(i+v) as usize] = 1;
            }
        }
    }
    dp.iter().enumerate().rev().find(|&(i, &v)| v == 1 && i % 10 != 0).map(|(i, _)| i as i32).unwrap_or(0)
}

fn read<T>() -> Result<T, T::Err> where T: std::str::FromStr {
    let mut line = String::new();
    let _ = io::stdin().read_line(&mut line);
    let words: Vec<&str> = line.split_whitespace().collect();
    words[0].parse()
}

fn main() {
    let n = read::<i32>().unwrap();
    let s: Vec<_> = (0..n).map(|_| read::<i32>().unwrap()).collect();
    let ans = solve(&s);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
ll n,m,i,j,k,a,b,c;
string str;
int main(){
	scanf("%lld",&n);
	cin>>str;
	if(n%2==1)
		printf("No\n");
	else
	{
		for(i=0;i<n/2;i++){
			if(str[i]!=str[i+n/2])
				break;
		}
		if(i==n/2)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(high_resolution_clock::now().time_since_epoch().count());
template<typename T> T ctmax(T &x, const T &y){ return x = max(x, y); }
template<typename T> T ctmin(T &x, const T &y){ return x = min(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto i = 0; i < n; ++ i){
		cin >> a[i];
	}
	vector<vector<long long>> dp(n + 1, vector<long long>(n + 1));
	for(auto l = 1; l <= n; ++ l){
		for(auto i = 0; i + l <= n; ++ i){
			int j = i + l;
			dp[i][j] = max(a[i] - dp[i + 1][j], a[j - 1] - dp[i][j - 1]);
		}
	}
	cout << dp[0][n];
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

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

#define ll long long
#define mod 1000000007
#define ffor(i,a,b) for(int i=a;i<b;i++)
#define bfor(i,a,b) for(int i=a-1;i>=b;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define mem(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sz(x) (int)x.size()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI 3.1415926535
#define lb lower_bound
#define ub upper_bound
#define bs binary_search

int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    string a="",b="";
    if(n%2)
    {
    	cout<<"No";
    	return 0;
    }
    ffor(i,0,n/2) a.pb(s[i]);
    ffor(i,n/2,n) b.pb(s[i]);
    if(a==b) cout<<"Yes";
    else cout<<"No";
    return 0;
}



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

int main() {
	int dataset[10001];
	int length,x;
	for (int i = 0;; i++){
		cin >> x;
		if (x==0){
			length = i;
			break;
		}
		dataset[i] = x;
	}
	for (int i = 0; i < length; i++){
		if (length>10000)
		{
			cout << "Too large" << endl;
			break;
		}
		cout << "Case " << i + 1 << ": " << dataset[i] << endl;
	}
	return 0;
}

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

using namespace std;

typedef long long int ll ; 

int  main()
{
    int t  ;
    
    t = 1 ;
    
    while(t--)
    {
        int n ;
        
        cin >> n ;
        
        int a[n] , countodd=0 , counteven=0 , minoddswap=n , minevenswap=n , maxodd , maxeven , secondminevenswap=n , secondminoddswap=n ;
        
        map<int,int> odd , even ;
        
        for(auto &i : a) cin >> i ;
        
        for(int i=0;i<n;i++)
        {
            if(i%2) 
            {
                if(odd.find(a[i])==odd.end()) odd[a[i]]=1 , countodd++ ;
                
                else odd[a[i]]++ ;
            }
            else
            {
                if(even.find(a[i])==even.end()) even[a[i]]=1 , counteven++ ;
                
                else even[a[i]]++ ;
            }
        }
        if((counteven==1)&(countodd==1))
        {
            if(a[0]==a[1]) cout << n/2 ;
            
            else cout << 0 ;
        }
        else
        {
            for(auto it=odd.begin();it!=odd.end();it++)
            {
                if((n/2)-(it->second) < minoddswap)
                {
                    maxodd = it->first ;
                    
                    minoddswap =(n/2) - (it->second) ;
                }
            }
            
            for(auto it=even.begin();it!=even.end();it++)
            {
                if((n/2)-(it->second) < minevenswap)
                {
                    maxeven = it->first ;
                    
                    minevenswap = (n/2) - (it->second) ;
                }
            }
        
            //if(countodd==1)
            {
                for(auto it = even.begin() ; it!=even.end() ; it++)
                {
                    if(it->first!=maxeven) secondminevenswap = min(secondminevenswap , (n/2) - (it->second)) ;
                }
            }
            //else if(counteven==1)
            {
                for(auto it = odd.begin() ; it!=odd.end() ; it++)
                {
                    if(it->first!=maxodd) secondminoddswap = min(secondminoddswap , (n/2) - (it->second)) ;
                }
            }
            if(maxodd==maxeven)
            {
               if(countodd==1) cout << minoddswap + secondminevenswap ;
               else if(counteven==1) cout << minevenswap + secondminoddswap ;
               else cout<<min(minoddswap + secondminevenswap , minevenswap + secondminoddswap) ;
            }
            else cout << minevenswap + minoddswap  ;
        }
        
    }
}

Measured memory_bytes: 8604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;
  ll ans = 1LL << 60;
  for (int i = 0; i <= 2 * max(X, Y); i++) {
    int rx = max(0, X - i / 2);
    int ry = max(0, Y - i / 2);
    ans = min(ans, (ll)i * C + rx * A + ry * B);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
#define p(x) cout<<(x)<<endl;
#define pv(v) for(auto a: v){ cout << a << endl; }

int main() {
  string n; cin >> n;

  if (n[0] == n[1] || n[1] == n[2] || n[2] == n[3] || n[3] == n[4]) {
        p("Bad");

  } else {
        p("Good");
  }
}


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

int main(){
	int a,b,c;
	cin >> a >> b >> c;
	cout << c << " " <<  a << " " <<  b << endl;
    return 0;
}



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

int main(){
    // input 
    int N, T;
    cin >> N >> T;

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

    //
    long long result = 0;
    for(int i=0; i<N-1; i++){
        result += min(T, list[i+1] - list[i]);
    }
    result += T;

    cout << result << endl;
    return 0;
}

Measured memory_bytes: 1024
import heapq

N, M = [int(n) for n in input().split()]
A = [-1*int(n) for n in input().split()]
heapq.heapify(A)
[heapq.heappush(A, -1*(-1*heapq.heappop(A)//2)) for _ in range(M)]   
print(-1*sum(A))

Measured memory_bytes: 14380
#include <iostream>
#include <iomanip>

int main()
{
	int h, w;
	std::cin >> h >> w;
	while (h != 0 || w != 0) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				std::cout << "#";
			}
			std::cout << std::endl;
		}
		std::cout << std::endl;
		std::cin >> h >> w;
	}
    return 0;
}


Measured memory_bytes: 3068
void main()
{
    string[] tmp = rdRow!string;
    long n = tmp[0].to!long, m = tmp[1].to!long;
    long[] p = new long[m];
    string[] s = new string[m];
    foreach (i; 0 .. m)
    {
        tmp = rdRow!string;
        p[i] = tmp[0].to!long;
        s[i] = tmp[1];
    }

    bool[] actof = new bool[n+1];
    long[] wacnt = new long[n+1];

    foreach_reverse (i; 0 .. m)
    {
        if (s[i] == "AC")
        {
            actof[p[i]] = true;
            wacnt[p[i]] = 0;
        }
        else
        {
            ++wacnt[p[i]];
        }
    }

    long ac, wa;
    foreach (i; 1 .. n+1)
    {
        if (actof[i])
        {
            ++ac;
            wa += wacnt[i];
        }
    }

    writeln(ac, " ", wa);
}

T rdElem(T = long)()
{
    //import std.stdio : readln;
    //import std.string : chomp;
    //import std.conv : to;

    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;

dchar[] rdDchar()
{
    //import std.conv : to;

    return rdStr.to!(dchar[]);
}

T[] rdRow(T = long)()
{
    //import std.stdio : readln;
    //import std.array : split;
    //import std.conv : to;

    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    //import std.range : iota;
    //import std.algorithm : map;
    //import std.array : array;

    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    //import std.range : iota;
    //import std.algorithm : map;
    //import std.array : array;

    return iota(col).map!(x => rdRow!T).array;
}

void wrMat(T = long)(T[][] mat)
{
    //import std.stdio : write, writeln;

    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 12668
using System;
using System.Collections.Generic;
using System.Windows;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    public class Program
    {
        static void Main(string[] args)
        {
            var r1 = ReadSplit();
            var n = r1[0].ToLong();
            var h = new long[110000][];
            var dp = new long[110000][];
            var INF = 9999999999999;

            for (int i = 0; i < 110000; i++)
            {
                dp[i] = new long[3];
                h[i] = new long[3];
            }

            for (int i = 0; i < n; i++)
            {
                var r = ReadSplit();
                for (int j = 0; j < 3; j++)
                {
                    h[i][j] = r[j].ToLong();
                }
            }

            dp[0][0] = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    for (int k = 0; k < 3; k++)
                    {
                        if (i != 0 && j == k) continue;
                        ChangekMax(ref dp[i + 1][k], dp[i][j] + h[i][k]);
                    }
                }
            }
            long ans = 0;
            for (int i = 0; i < 3; i++)
            {
                ChangekMax(ref ans, dp[n][i]);
            }
            WriteRead(ans);
        }

        public static string Read()
        {
            return Console.ReadLine();
        }

        public static string[] ReadSplit()
        {
            return Console.ReadLine().Split(' ');
        }

        public static void WriteRead(object str)
        {
            Console.WriteLine(str);
            Read();
        }

        public static void Write(object str)
        {
            Console.WriteLine(str);
        }

        private static bool ChangeMin<T>(ref T a, T b) where T : IComparable
        {
            if (a.CompareTo(b) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }

        private static bool ChangekMax<T>(ref T a, T b) where T : IComparable
        {
            if (b.CompareTo(a) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }
    }
}


public static class Extentions
{
    public static int ToInt32(this object obj)
    {
        return int.Parse(obj.ToString());
    }

    public static long ToLong(this object obj)
    {
        return long.Parse(obj.ToString());
    }

    public static decimal ToDecimal(this object obj)
    {
        return decimal.Parse(obj.ToString());
    }

    public static double ToDouble(this object obj)
    {
        return double.Parse(obj.ToString());
    }

    public static T2 GetValueZero<T1, T2>(this Dictionary<T1, T2> d, T1 key) where T2 : struct
    {
        T2 value;
        if (d.TryGetValue(key, out value))


        {
            return value;
        }
        return new T2();
    }
}



Measured memory_bytes: 31160
# -*- coding: utf-8 -*-
'''
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_A&lang=jp
???????¨???????
?????§??£?????¢
'''

H, W = map(int, input().split())
C = list()
maxWidth = 0

for h in range(H):
    C.append(list(map(int, input().split())))

dp = dict()
for h in range(H+1):
    dp[(h, 0)] = 0

for w in range(W+1):
    dp[(0, w)] = 0

for h in range(1, H+1):
    for w in range(1, W+1):
        if C[h-1][w-1] == 1:
            dp[(h, w)] = 0
        else:
            dp[(h, w)] = min(dp[(h-1, w-1)], dp[(h-1, w)], dp[(h, w-1)]) + 1
            maxWidth = max(dp[(h, w)], maxWidth)

print(maxWidth**2)

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

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

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    ll n; cin >> n;
    vector <ll> cnt(n+1, 1);
    for(ll i=1; i<n/2+1; i++){
        ll j = i*2;
        while(j < n+1){
            cnt[j]++;
            j += i;
        }
    }
    ll ans = 0;
    REP(i, n+1){
        ans += cnt[i]*i;
    }
    cout << ans << endl;
    return 0;
}

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

template<class t> void vin(vector<t>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

struct rect {
    int miw, maw, mih, mah;
    rect() {}
    rect(int h, int w) :miw(w), maw(w), mih(h), mah(h) {}
    void update(int h, int w) {
        miw = min(miw, w); maw = max(maw, w);
        mih = min(mih, h); mah = max(mah, h);
    }
};
int h, w;
vector<string> bag;
vector<string> tmp;
vector<char> layer;
map<char, rect> rects;

void fill(char type) {
    rect rt = rects[type];
    for (int y=rt.mih; y<=rt.mah; ++y) {
        for (int x=rt.miw; x<=rt.maw; ++x) {
            tmp[y][x] = type;
        }
    }
    return;
}

bool is_safe() {
    rep(r, h) rep(c, w) {
        if (tmp[r][c] != bag[r][c]) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    rep(i, n) {
        cin >> h >> w;
        bag.resize(h);
        rects.clear();
        layer.clear();

        rep(r, h) {
            cin >> bag[r];
            rep(c, w) {
                if (bag[r][c] == '.') continue;
                if (rects.count(bag[r][c]) == 0) {
                    rects[bag[r][c]] = rect(r, c);
                    layer.push_back(bag[r][c]);
                }
                else {
                    rects[bag[r][c]].update(r, c);
                }
            }
        }

        bool ok = false;
        sort(layer.begin(), layer.end());
        do {
            tmp = bag;
            rep(i, layer.size()) {
                fill(layer[i]);
            }
            if (is_safe()) {
                ok = true;
                break;
            }
        } while (next_permutation(layer.begin(), layer.end()));

        cout << (ok ? "SAFE" : "SUSPICIOUS") << endl;
    }
}



Measured memory_bytes: 3020
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};


int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    string s;
    cin>>s;
    int cntr=0;
    rep(i,3) if(s[i]=='R') cntr ++;
    if(cntr!=2){
        cout<<cntr<<endl;
        return 0;
    }
    if(s[1]=='S') cout<<1<<endl;
    else cout<<2<<endl;
}/*
./problem.exe
*/

Measured memory_bytes: 3596