akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;

ll mpow(ll x, ll n){
  if(n == 0) return 1;
  return mpow(x * x, n / 2) * ((n % 2)? x: 1);
}

int main(){
  int n, k; cin >> n >> k;
  vector<int> a(k, 0);

  for(int i=1; i<=n; i++){
    a[i % k]++;
  }

  ll ans = 0;
  ans += mpow(a[0], 3);
  if(k % 2 == 0) ans += mpow(a[k/2], 3);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
import sys

n=int(input())
chara = list(map(int,input().split()))
chara.append(-1)
manu = [0]*n  

for i in range(n,0,-1):
    saga=0
    for j in range (i-1,-1,-1):
        if chara[j]==j+1:
            for k in range (j,n):
                chara[k]=chara[k+1]

            manu[i-1]=j+1
            saga=1
            break
    if saga==0:
        print(-1)
        sys.exit()


for i in range(n):
    print(manu[i])

Measured memory_bytes: 3064
H, W, K = map(int, input().split())

s = [0]*H
z = 1
for i in range(H):
    x = input()
    ary = []
    for j in x:
        if j == "#":
            ary.append(z)
            z += 1
        else:
            ary.append(0)
    s[i] = ary

a = s
row = 0
for i in a:
    flag = 0
    N_L = 0
    for j in i:
        if j > 0:
            N_L = j
            break
    flag = 0
    col = 0
    xx = 0
    for j in i:
        if j == 0 and flag == 0:
            a[row][col] = N_L
        elif j>0:
            xx = j
            flag = 1
        else:
            a[row][col] = xx
        col += 1
    row += 1

flag = 0
ary = []
for i in range(H):
    if a[i][0] == 0 and flag == 0:
        pass
    elif a[i][0]>0:
        ary = a[i]
        flag = 1
    else:
        a[i] = ary

for i in range(H):
    if a[H-1-i][0] == 0 and flag == 0:
        pass
    elif a[H-1-i][0]>0:
        ary = a[H-1-i]
        flag = 1
    else:
        a[H-1-i] = ary


for i in a:
    print(*i)

Measured memory_bytes: 7504
#include <stdio.h>
#define MAX(a,b) (a>b?a:b)
int main()
{
    int n, i, max=0, p[10], sum=0;
    scanf("%d",&n);
    for(i=0;i<n;i++) {
        scanf("%d",&p[i]);
        max = MAX(max,p[i]);
        sum += p[i];
    }
    sum -= max/2;
    printf("%d",sum);
    return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;

int main() {
	long long int N, L, M, R; cin >> N >> L >> M >> R;
	R *= 2;
	M *= 2;
	vector<pair<long long int, long long int>>ps;
	ps.push_back(make_pair(0, 0));
	bool ok = true;
	for (int i = 0; i < N; ++i) {
		int W; cin >> W;
		{
			vector<pair<long long int, long long int>>newps;
			for (auto p : ps) {
				newps.emplace_back(p.first - L*W, p.second - R*W);
				newps.emplace_back(p.first + R*W, p.second + L*W);
			}
			ps = newps;
		} 
		{
			vector<pair<long long int, long long int>>newps;
			for (auto p : ps) {
				if (p.first > p.second)continue;
				if (p.first > M)continue;
				if (p.second > M)p.second = M;
				if (p.second < -M)continue;
				if (p.first < -M)p.first = -M;
				newps.push_back(p);
			}
			ps = newps;
		}
		if (!ps.empty()) {
			sort(ps.begin(), ps.end());
			vector<pair<long long int, long long int>>nextps;
			{
				nextps.emplace_back(ps[0]);
				for (int i = 0; i < ps.size() - 1; ++i) {
					const int b = nextps.back().second;
					if (b >= ps[i + 1].first) {
						nextps.back().second = max(nextps.back().second, ps[i + 1].second);
					}
					else {
						nextps.emplace_back(ps[i + 1]);
					}
				}
			}
			ps = nextps;
		}
		else {
			ok = false;
			break;
		}
		
	}
	if (ok) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
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;}
//自作関数
template<class T> ll llpow(T x,T n){ll ans=1;while(n--){ans*=x;}return ans;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int n,w;
int main(){
    cin>>n>>w;
    int weight[w];
    int value[w];
    rep(i,n)cin>>weight[i]>>value[i];
    ll dp[n+10][w+10];
    rep(i,n+10)rep(j,w+10)dp[i][j]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=w;j++){
           if(j-weight[i]>=0)chmax(dp[i+1][j],dp[i][j-weight[i]]+value[i]);

           chmax(dp[i+1][j],dp[i][j]);
        }
    }
    cout<<dp[n][w]<<endl;
    return 0;
}




Measured memory_bytes: 86144
def main():
    s = input()
    K = int(input())
    lst = sorted(set(s))
    ans = []

    def dfs(c):
        if len(ans) < K:
            ans.append(c)
            for li in lst:
                if c + li in s:
                    dfs(c + li)
        return

    for li in lst:
        dfs(li)
    print(ans[K - 1])
    return


main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1LL<<60;
const ll mod=1000000007;

int main(void){
    ll a,b,v,w,t;
    cin>>a>>v>>b>>w>>t;
    ll c=abs(b-a);
    ll x=max(ll(0),v-w);
    if(c<=x*t) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <iostream>
#define MAX 1000000
#define MAX_X 1000000000
using namespace std;

int main() {
  long long tri[MAX];
  for (int i = 0; ; i++) {
    tri[i] = i * (i + 1) / 2;
    if (tri[i] > MAX_X) break;
  }

  int x;
  cin >> x;
  int res, p;
  for (int i = 0; ; i++) {
    if (tri[i] >= x) {
      cout << i << endl;
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 2432
//Code is like humor. When you have to explain it, it’s bad.
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#include <bits/stdc++.h>
#define MOD 1000000007
#define int long long
using namespace std;
#define ss second
#define ff first
#define N 100005
string A[N];

void calc()
{
    int i,j,k;
    A[0]="0";
    for(i=1;i<N;i++)
    {
        string s=A[i-1];
        int l = s.length();
        for(j=l-1;j>=0;j--)
        if(j!=0)
        {
            if((s[j]-s[j-1])<1 and s[j]!='9')
            {
                s[j]=s[j]+1;
                for(k=j+1;k<l;k++)
                if(s[k-1]=='0')     s[k]='0';
                else                s[k]=s[k-1]-1;
                break;
            }
        }
        else
        {
            if(s[j]!='9')   s[j]=s[j]+1;
            else            s[j]='0';
            
            for(k=j+1;k<l;k++)
            if(s[k-1]=='0')     s[k]='0';
            else                s[k]=s[k-1]-1;
            
            if(s[j] == '0' )
                s = '1'+s;
        }
        A[i]=s;
    }
    // for(i=1;i<40;i++)
    // cout<<A[i]<<' ';
}
int32_t main()
{
    fastio;
    calc();
    int T,n,m,i,j,k,a,b,c;
    cin>>n;
    cout<<A[n];
    return 0;
}

Measured memory_bytes: 6268
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <map>
using namespace std;

int main() {
    int n, m, c;
    int count = 0;
    cin >> n >> m >> c;
    vector<int> b(m);
    vector<vector<int>> a(n, vector<int> (m));
    for (int i = 0; i < m; i++) {
        cin >> b.at(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a.at(i).at(j);
        }
    }
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            sum += a.at(i).at(j) * b.at(j);
        }
        sum += c;
        if (sum > 0) count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 256
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]:
                break
            elif A[i][k] > A[i][j] + A[j][k]:
                print(-1)
                exit()
        else:
            ans += A[i][j]

print(ans)

Measured memory_bytes: 43868
# -*- coding: utf-8 -*-
#<参考>https://atcoder.jp/contests/abc178/submissions/16700679
import sys
from heapq import *
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(map(int,readline().split()))
B = list(map(int,readline().split()))

countA = [0]*(N+1)
countB = [0]*(N+1)
for i in range(N):
    countA[A[i]] += 1
    countB[B[i]] += 1

q = []
onlyA = []
onlyB = []
for i in range(N+1):
    if countA[i] and countB[i]:
        heappush(q,(-countA[i]-countB[i],i))
        continue
    for _ in range(countA[i]):
        onlyA.append(i)
    for _ in range(countB[i]):
        onlyB.append(i)
        
heapify(q)

if q and -q[0][0] > N:
    print('No')
    sys.exit()
print('Yes')

ans = []

while q:
    _,x = heappop(q)
    if q:
        _,y = heappop(q)
        flag = True
    else:
        y = onlyB.pop()
        flag = False
    countA[x] -= 1 
    countB[y] -= 1
    ans.append((x,y))
    if countA[x]:
        heappush(q,(-countA[x]-countB[x],x))
    else:
        for _ in range(countB[x]):
            onlyB.append(x)
            
    if flag and countB[y]:
        heappush(q,(-countA[y]-countB[y],y))
    if flag and not countB[y]:
        for _ in range(countA[y]):
            onlyA.append(y)

while onlyA:
    x,y = onlyA.pop(),onlyB.pop()
    ans.append((x,y))

ans.sort()
X,Y = zip(*ans)
print(*Y)        


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

using namespace std;

typedef long long int ll;

#define FOR(i,l,r) for(i=l;i<r;i++)

#define REP(i,n) FOR(i,0,n)

#define ALL(x) x.begin(),x.end()

#define P pair<ll,ll>

#define F first

#define S second

signed main(){

  ll K,A,B;cin>>K>>A>>B;

  if((A-1)/K<B/K)cout<<"OK"<<endl;
  else cout<<"NG"<<endl;

  return 0;

}

Measured memory_bytes: 3632
#include <iostream>

using namespace std;

int main()
{
	int A,B;
	cin >> A >> B;

	if (A >= 13) {
		cout << B << endl;
	}
	else if (6 <= A && A <= 12) {
		cout << B / 2 << endl;
	}
	else if (A <= 5) {
		cout << 0 << endl;
	}


}





Measured memory_bytes: 384
S = input()

if 1 <= int(S[:2]) <= 12:
  if 1 <= int(S[2:]) <= 12:
    print('AMBIGUOUS')
  else:
    print('MMYY')
elif 1 <= int(S[2:]) <= 12:
  print('YYMM')
else:
  print('NA')

Measured memory_bytes: 3060
import java.util.*;
public class Main{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[3];
        for(int i = 0;i < 3; i++)
        {
            a[i] = sc.nextInt();
        }
        sc.close();

        Arrays.sort(a);
        for(int i = 0; i< 3; i++)
        {
            if(i > 0) System.out.print(" ");
            System.out.print(a[i] );
        }
        System.out.println();
    }
}


Measured memory_bytes: 26340
#include<stdio.h>

#define MAX 101
#define INF -1
#define WHITE 1
#define GRAY 2
#define BLACK 3

typedef struct{
  int k;
  int v[MAX];
}node;

int n,tail=0,head=0;
int color[MAX],d[MAX],Q[MAX];
node G[MAX];

void bfs(int);
void enqueue(int);
int dequeue(void);

int main(){
  int i,j,u;

  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&u);
    scanf("%d",&G[u].k);
    for(j=0;j<G[i].k;j++) scanf("%d",&G[i].v[j]);
  }
  
  bfs(1);

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

void bfs(int s){
  int i,u,v;

  for(i=1;i<=n;i++){
    color[i]=WHITE;
    d[i]=INF;
  }
  
  color[s]=GRAY;
  d[s]=0;
  enqueue(s);

  while(head!=tail){
    u=dequeue();
    for(i=0;i<G[u].k;i++){
      v=G[u].v[i];
      if(color[v]==WHITE){
	color[v]=GRAY;
	d[v]=d[u]+1;
	enqueue(v);
      }
    }
    color[u]=BLACK;
  }

}

void enqueue(int x){
  Q[tail]=x;

  if(tail+1==MAX) tail=0;
  else tail++;
}

int dequeue(void){
  int x;

  x=Q[head];

  if(head+1==MAX) head=0;
  else head++;

  return x;
}



Measured memory_bytes: 2108
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>

#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)
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 105
const int INF = 1e9 + 7;



int main() {

	int a, b, c;
	cin >> a >> b >> c;

	int ans = 7 * (c / (7 * a + b));
	c -= (7 * a + b) * (c / (7 * a + b));
	
	int cnt = 0;
	while (c > 0)
	{
		ans++;
		c -= a;
		cnt++;
		if (cnt == 7)
		{
			c -= b;
			cnt = 0;
		}
	}

	cout << ans << endl;
}





Measured memory_bytes: 3092
/*
时间:2020-8-6
书籍：算法和数据结构
内容：归并排序
页数：P125
*/
#include<iostream>
using namespace std;
int partition(int A[], int p, int r)
{
	int base = A[r];
	int i = p;
	for (int j = p; j < r; ++j)
	{
		if (A[j] <= base)
		{
			swap(A[i], A[j]);
			++i;
		}
	}
	swap(A[i], A[r]);
	return i;                         //返回分割点的下表
}

int main() 
{
	int n;
	cin >> n;
	int* A = new int[n];
	for (int i = 0; i < n; ++i)
		cin >> A[i];
	int part = partition(A, 0, n - 1);
	for (int i = 0; i < n - 1; ++i)
	{
		if (i == part)
			cout << "[" << A[i] << "]" << " ";
		else
			cout << A[i]<<" ";
	}
	cout << A[n - 1]<<endl;
	delete[]A;
	return 0;
}


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

using namespace std;

double dp[301][301][301];
int n;

double cal(int x1, int x2, int x3){
    if(x1 == 0 && x2 == 0 && x3 == 0)
        return 0;
    
    if(dp[x1][x2][x3] != 0)return dp[x1][x2][x3];

    double res1, res2, res3;
    res1 = res2 = res3 = 0;
    
    if(x1 > 0)res1 = cal(x1-1, x2, x3) * x1;
    if(x2 > 0)res2 = cal(x1+1, x2-1, x3) * x2;
    if(x3 > 0)res3 = cal(x1, x2+1, x3-1) * x3;
    
    return dp[x1][x2][x3] = (res1 + res2 + res3 + n) / (x1 + x2 + x3);
}

int a[4];

void solve(){
    
    cin >> n;
    
    for(int i = 1;i <= n;++i){
        int x;
        cin >> x;
        ++a[x];
    }
    
    cout << fixed << setprecision(9) << cal(a[1], a[2], a[3]);
}

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

Measured memory_bytes: 213248
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<pair<ll, ll>> pll;
 
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
 
const long double PI = acos(-1);
 
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}


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

  string s;
  cin >> s;
  ll ans = 0;
  ans += (s[0]=='+'?1:(-1));
  ans += (s[1]=='+'?1:(-1));
  ans += (s[2]=='+'?1:(-1));
  ans += (s[3]=='+'?1:(-1));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;

#define ll long long
#define vvi vector< vector<int> >
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

string func2(char people,string str){
	string newstr;
	if(people=='J'){
		newstr+=str[str.size()-1];
		FOR(i,0,str.size()-1){
			newstr += str[i];
		}
	}
	if(people=='C'){
		FOR(i,1,str.size()){
			newstr += str[i];
		}
		newstr+=str[0];
	}
	if(people=='E'){
		if(str.size()%2==1){
			FOR(i,str.size()/2+1,str.size()){
				newstr += str[i];
			}
			newstr += str[(str.size()-1)/2];
			FOR(i,0,str.size()/2){
				newstr += str[i];
			}
		}else{
			FOR(i,str.size()/2,str.size()){
				newstr += str[i];
			}
			FOR(i,0,str.size()/2){
				newstr += str[i];
			}			
		}
	}
	if(people=='A'){
		FOR(i,0,str.size()){
			newstr += str[str.size()-i-1];
		}
	}
	if(people=='M'){
		FOR(i,0,str.size()){
			if(('0'<= str[i])&&(str[i]<='9')){
				if(str[i]!='9') newstr += (str[i]+1);
				else newstr += '0';
			}else{
				newstr += str[i];
			}
		}
	}
	if(people=='P'){
		FOR(i,0,str.size()){
			if(('0'<= str[i])&&(str[i]<='9')){
				if(str[i]!='0') newstr += (str[i]-1);
				else newstr += '9';
			}else{
				newstr += str[i];
			}
		}
	}
	return newstr;
}
int main(){
	int n;
	cin >> n;
	REP(i,n){
		string plist,str;
		cin >> plist >> str;
		FOR(j,0,plist.size()){
			char pp = plist[plist.size()-1-j];
			str = func2(pp,str);
		}
		cout << str << endl;
	}
}

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

int f[7][7][7],N,M;
int dx[] ={0,0,-1,1,0,-1,1,-1,1};
int dy[] ={0,-1,0,0,1,-1,-1,1,1};

int dfs(int x, int y, int z, int c,int m,int mz, bool d)
{
	int s=1;
	int tx=x, ty=y,tz=z;
	if(d) tx+=dx[m], ty+=dy[m], tz+=mz;
	else  tx-=dx[m], ty-=dy[m], tz-=mz;
	if(tx<0||ty<0||tz<0||tx>=N||ty>=N||tz>=N) return s;
	if(f[tx][ty][tz]!=c) return s;
	s+=dfs(tx,ty,tz,c,m,mz,d);
	
	return s;
}

int main()
{
	int P;
	while(cin >> N >> M >> P, (N||M||P))
	{
		memset(f,0,sizeof(f));
		int c=0, e=0;
		for(int j=1; j<=P; j++)
		{
			c=(c==1?2:1);
			int x,y,z=0;
			cin >> x >> y;
			x--,y--;
			while(1)
			{
				if(f[x][y][z]==0)
				{
					f[x][y][z]=c;
					break;
				}
				z++;
			}
			
			if(e!=0) continue;
			
			for(int mz=-1; mz<=1; mz++)
			for(int i=0; i<9; i++)
			{
				int t=1;
				if(i==0&&mz==0) continue;
				for(int d=0; d<2; d++)
				{
					int tx=x, ty=y,tz=z;
					
					if(d) tx+=dx[i], ty+=dy[i], tz+=mz;
					else  tx-=dx[i], ty-=dy[i], tz-=mz;
					
					if(tx<0||ty<0||tz<0||tx>=N||ty>=N||tz>=N) continue;
					if(f[tx][ty][tz]!=c) continue;
					
					t+=dfs(tx,ty,tz,c,i,mz,d);
					
				}
				if(t>=M) e=j;
			}
		}
		
		if(e==0) cout << "Draw" << endl;
		else
		{
			cout << (e%2==0?"White ":"Black ") << e << endl;
		}
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(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 fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (ll)(1E9+7)
#define PI 3.1415926535897932384

template <class T>ostream &operator<<(std::ostream &o, const vector<T> &v)
{
	rep(i, v.size()) {
		o << (i > 0 ? " " : "") << v[i];
	}
	return o;
}

int main() {
	int a, b, c, x,ans=0;
	cin >> a >> b >> c >> x;
	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			for (int k = 0; k <= c; k++) {
				if (i * 500 + j * 100 + k * 50 == x) {
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
}


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

#define ll long long
#define ull unsigned long long

using namespace std;

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

	vector <int> p(n, 0);
	for (int ii = 0; ii < n; ++ii){
		cin >> p[ii];
	}

	int ans = 0;
	for (int ii = 1; ii < n-1; ++ii){
		bool cond1 = (p[ii-1] < p[ii]) && (p[ii] < p[ii+1]);
		bool cond2 = (p[ii+1] < p[ii]) && (p[ii] < p[ii-1]);
		if (cond1 || cond2){
			ans++;
		}
	}

	cout << ans << "\n";	

	return 0;
}


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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP0(i, n) for (int i = (n)-1; i >= 0; --i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define RREP1(i, n) for (int i = (n); i >= 1; --i)
#define pow10(n) int(1e##n + n)

typedef long long LL;
typedef pair<int, int> P;

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0E-14;

struct pos
{
    int x;
    int y;
};

LL d[90001];

void solve()
{
    int H, W, D;
    cin >> H >> W >> D;
    map<int, pos> num_pos;
    REP1 (i, H)
    {
        REP1 (j, W)
        {
            int A;
            cin >> A;
            num_pos[A] = pos{i, j};
        }
    }

    for (int i = D + 1; i <= H * W; i++)
    {
        pos pL = num_pos[i], pDL = num_pos[i - D];
        d[i] = d[i - D] + abs(pL.x - pDL.x) + abs(pL.y - pDL.y);
    }

    int Q;
    cin >> Q;
    REP1 (_, Q)
    {
        int L, R;
        cin >> L >> R;
        std::cout << d[R] - d[L] << endl;
    }
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(20);
    solve();
    return 0;
}


Measured memory_bytes: 7424
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int r, degree;
    int sum_degree = 0;
    double wx = 0, wy = 0;
    char comma;

    while (true) {
        cin >> r >> comma >> degree;
        if (!r && !degree) {
            break;
        }

        // the input of sin and cos is radian
        wx += r * sin(M_PI / 180.0 * sum_degree);
        wy += r * cos(M_PI / 180.0 * sum_degree);

        sum_degree = (sum_degree + degree) % 360;
    }

    cout << (int)wx << "\n" << (int)wy << endl;

    return 0;
}

Measured memory_bytes: 1168
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		read();
	}

	private static void read() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();	
		str = str.replaceAll("\\?", "D");
		System.out.println(str);
		br.close();
	}
}

Measured memory_bytes: 49896
N = int(input())
T = []
for i in range(N):
    a,b = map(int,input().split())
    T.append({'A':a, 'B':b})
T = sorted(T, key=lambda x: x['B'])

ans = 'Yes'
t = 0
for task in T:
    t += task['A']
    if t > task['B']:
        ans = 'No'

print(ans)


Measured memory_bytes: 80264
N = int(input())
ans = 0

for i in range(1,N+1):
    if i >= 100000:
        continue    
    elif i >= 10000:
        ans += 1
    elif i >= 1000:
        continue
    elif i >= 100:
        ans += 1
    elif i >= 10:
        continue
    else:
        ans += 1

print(ans)

Measured memory_bytes: 2940
def resolve():
    a, b = input().split()
    ab_list = []
    
    ab = a*int(b)
    ba = b*int(a)

    ab_list.append(ab)
    ab_list.append(ba)
 
    ab_list = sorted(ab_list)
 
    print(ab_list[0])
 
if __name__ == "__main__":
    resolve()

Measured memory_bytes: 3060
n, m = map(int, input().split())

a_list = []
b_list = []

for i in range(n):
    a_list = list(map(int,input().split()))
    b_list.append(a_list)

b_list.sort()

buy = 0
money = 0

for i in range(n):
    if buy + b_list[i][1] <= m:
        buy = buy + b_list[i][1]
        money = money + b_list[i][0] * b_list[i][1]
    else:
        need = m - buy
        money = money + b_list[i][0] * need
        break

print(money)


Measured memory_bytes: 27760
#include <algorithm>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <stdio.h>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const double PI = 3.1415926535897932;

/* a と b の最大公約数を返す関数 */
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}



int main()
{
	int N;
	cin >> N;
	vector<long long> Ai(N, 0);
	rep(i, N) cin >> Ai.at(i);

	sort(Ai.begin(), Ai.end());
	reverse(Ai.begin(), Ai.end());

	ll ans = 0;
	int t = N - 1;
	rep(i, N)
	{
		int lim = 2;
		if (i == 0) lim = 1;
		rep(j, lim)
		{
			if (t > 0)
			{
				ans += Ai[i];
				t--;
			}
		}
	}

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

Measured memory_bytes: 4828
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define MAX 9223372036854775807
#define MIN -9223372036854775807
#define PI 3.141592653589
#define setbits(n) __builtin_popcountll(n)
const ll mod=1e9+7;

const int N=2e3+1;
ll dp[N];

ll go(ll rem){
    if(rem==0) return 1;
    if(dp[rem]!=-1)
        return dp[rem];
    ll ans=0;
    for(int i=3;i<=rem;i++)
        ans=(ans+go(rem-i))%mod;
    return dp[rem]=ans;
}

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll T=clock();

    ll s;
    cin>>s;
    memset(dp,-1,sizeof(dp));
    cout<<go(s);


 
 
    cerr<<"\n\nTIME: "<<(double)(clock()-T)/CLOCKS_PER_SEC<<" sec\n";
    T = clock();
    return 0;
}

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

int main() {
 int n,cnt1=0,cnt2=0;
 cin >> n;
 vector<long long> h(n);
  for(int i=0;i<n;i++){
    cin >>h[i];
  }
  for(int i=1;i<n;i++){
    if(h[i]<=h[i-1]){
      cnt2++;
    }
    else{
      cnt1=max(cnt1,cnt2);
      cnt2=0;
    }
  }
  cnt1=max(cnt1,cnt2);
  cout << cnt1 << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()
template <int MOD>
class ModInt {
  long long x;

 public:
  ModInt(long long v = 0) : x(v % MOD) {
    if (x < 0) x += MOD;
  }

  ModInt& operator+=(const ModInt& r) {
    x += r.x;
    if (x >= MOD) x -= MOD;
    return *this;
  }

  ModInt& operator-=(const ModInt& r) {
    x -= r.x;
    if (x < 0) x += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& r) {
    x = (x * r.x) % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt& r) {
    *this *= r.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt& r) const { return ModInt(*this) += r; }
  ModInt operator-(const ModInt& r) const { return ModInt(*this) -= r; }
  ModInt operator*(const ModInt& r) const { return ModInt(*this) *= r; }
  ModInt operator/(const ModInt& r) const { return ModInt(*this) /= r; }
  bool operator==(const ModInt& r) const { return x == r.x; }
  bool operator!=(const ModInt& r) const { return x != r.x; }

  ModInt inverse() const {
    long long a = x, b = MOD, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt<MOD> pow(long long n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream& operator<<(ostream& os, const ModInt& x) { return os << x.x; }

  friend istream& operator>>(istream& is, ModInt& x) { return is >> x.x; }

  int getMod() { return MOD; }
};

using mint = ModInt<1000000007>;

int N;
vector<vector<int>> G;
vector<vector<mint>> memo;

mint dfs(int u, int p, int c) {
  if (memo[u][c] != -1) return memo[u][c];

  mint res = 1;
  for (int v : G[u]) {
    if (v == p) continue;
    res *= (c == 0 ? dfs(v, u, 0) + dfs(v, u, 1) : dfs(v, u, 0));
  }
  return memo[u][c] = res;
}

int main() {
  cin >> N;
  G.resize(N);
  memo.resize(N, vector<mint>(2, -1));

  rep(i, N - 1) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    G[x].push_back(y);
    G[y].push_back(x);
  }

  cout << dfs(0, -1, 0) + dfs(0, -1, 1) << endl;

  return 0;
}


Measured memory_bytes: 19584
n = int(input())
if 1 <= n < 105:
    print("0")
elif 105 <= n < 135:
    print("1")
elif 135 <= n < 165:
    print("2")
elif 165 <= n < 189:
    print("3")
elif 189 <= n < 195:
    print("4")
elif 195 <= n <= 200:
    print("5")

Measured memory_bytes: 3060
#展望台i：1 ~ Nこの展望台
#Hi: 展望台iの高さ

from copy import deepcopy
from pprint import pprint

n,m = map(int, input().split())

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

nolist = [0] * n

for _ in range(m):
    a,b = map(int,input().split())
    if h[a-1] > h[b-1]:
        nolist[b-1] = 1
    elif h[a-1] < h[b-1]:
        nolist[a-1] = 1
    elif h[a-1] == h[b-1]:
        nolist[a-1] = 1
        nolist[b-1] = 1

#counter = 0
#for j in range(n):
#    if maxlist[j] ==j and pairlist[j] != 1:
#        counter += 1

#print(maxlist)
#print(pairlist)

print(nolist.count(0))

exit()

Measured memory_bytes: 84808
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
	int n;
	int ans = 0;
	int minOne = 10;
	vector<int> v( 5 );
	for( int i = 0; i < 5; i++ )
	{
		
		cin >> n;
		if( n % 10 )
		{
			ans += n + ( 10 - n % 10 );
			minOne = min( minOne, n % 10 );
		}
		else
			ans += n;	
	}

	if( minOne == 10 )
	{
		cout << ans << endl;
	}
	else
	{
		cout << ans - 10 + minOne << endl;
	}

	return 0;
}

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

typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;

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

    if(s.size()<4)  puts("No");
    else{
        if (s[0] == 'Y' && s[1] == 'A' && s[2] == 'K' && s[3] == 'I' )
            puts("Yes");
        else    puts("No");
    }

    return 0;
}

Measured memory_bytes: 3600
I=lambda:map(int,input().split())
n,p = I()
s=[0]
for i in I():
  s += [s[-1]+i]

for t in range(1,n + 1):
  m = 5 * s[n] + t * p
  for i in range(n - t * 2,0,-t):
    m += 2 * s[i]
  a = m if t == 1 else min(a,m)
print(a + n * p)

Measured memory_bytes: 27244
#include<iostream>

int main(){
	
	int a,b,c,more,less;
	std::cin >>a>>b>>c;
	
	less = b<c?b:c;
	more = b>c?b:c;
	
	if (a<=less && a<=more) std::cout << a <<" "<< less <<" "<< more <<"\n";
	else if (a>=less && a<=more)std::cout<< less<<" "<<a<<" "<<more<<"\n";
	else std::cout << less <<" "<< more<<" "<<a<<"\n";
	
	return 0;
	
}

Measured memory_bytes: 1164
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;

ll gcd(ll a,ll b){
  ll r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
return b;
}


int main(){
  ll ans=0;
  cin >> n >> k;
  cout<<n*k/(gcd(n,k))<<endl;
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[][] b = new int[3][3];

		for (int x = 0; x < 3; x++) {
			String[] foo = br.readLine().split(" ");
			for (int y = 0; y < 3; y++) {
				b[x][y] = Integer.parseInt(foo[y]);
			}
		}

		int a2 = 0;
		int a3 = 0;
		int b1 = 0;
		int b2 = 0;
		int b3 = 0;

		for (int a1 = 0; a1 < 100; a1++) {
			b1 = b[0][0] - a1;
			b2 = b[0][1] - a1;
			b3 = b[0][2] - a1;

			int[] bls = { b1, b2, b3 };

			for (int x = 0; x < 3; x++) {
				if (x == 0) {
					a2 = b[1][x] - bls[x];
					a3 = b[2][x] - bls[x];
				} else {
					if (a2 != b[1][x] - bls[x]) {
						System.out.println("No");
						System.exit(0);
					}
					if (a3 != b[2][x] - bls[x]) {
						System.out.println("No");
						System.exit(0);
					}
					a2 = b[1][x] - bls[x];
					a3 = b[2][x] - bls[x];

				}
			}

		}
		System.out.println("Yes");

	}
}


Measured memory_bytes: 21460
//****** @mdazmat9 **********
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define EB emplace_back
#define PB push_back
#define endl "\n"
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int fast_pow(int x, int y, int p);


void solve() {
    int n;cin>>n;
    map<string ,int> mp;
    for(int i=0;i<n;i++){
        string s;cin>>s;
        mp[s]++;
    }
    int mx=0;
    for(auto x: mp){
        mx=max(mx,x.S);
    }
    for(auto x:mp){
        if(x.S==mx){
            cout<<x.F<<endl;
        }
    }

}

int32_t main() {
    IOS;
    int test = 1;
     //cin >> test;
    while (test--) {
        solve();
    }
    return 0;
}
int fast_pow(int x, int y, int p) {
    int res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

Measured memory_bytes: 23808
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long 
#define ld long double
long long const inf = 1e18;
int const mxn = 2e5+10;
 
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
 
 
 
 long long sum ;
 
int main(){
	long long h,a;
	cin>>h>>a;
	for (int i = 0;i<a;i++){
		int l ;
		cin>>l;
		sum+=l;
	}
	if (sum>=h)
		cout<<"Yes";
	else
		cout<<"No";
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <utility>
#include <numeric>

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;

const ullong MOD = 1000000000 + 7;

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

	double t, a;
	cin >> t >> a;

	int id = -1;
	double minv = 1000000000;
	for (int i = 0; i < n; i++)
	{
		double x;
		cin >> x;

		double m = abs(a - (t - x * 0.006));
		if (minv > m)
		{
			id = i + 1;
			minv = m;
		}
	}

	cout << id << endl;
}

Measured memory_bytes: 256
h, w = gets.strip.split.map(&:to_i)
c = 10.times.map { gets.strip.split.map(&:to_i) }
a = h.times.map { gets.strip.split.map(&:to_i) }

10.times do |via|
  10.times do |from|
    10.times do |to|
      c[from][to] = c[from][via] + c[via][to] if c[from][to] > c[from][via] + c[via][to]
    end
  end
end

p a.flatten.reject {|e| e==-1 }.map {|e| c[e][1] }.inject(0, :+)

Measured memory_bytes: 3632
import java.io.*;
 
class Main {
  public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
     
    String[] strAry = str.split(" ");
     
    int a = Integer.parseInt(strAry[0]);
    int b = Integer.parseInt(strAry[1]);
    int c = Integer.parseInt(strAry[2]);

    if(a < b && b < c){
    	System.out.println("Yes");
    }else{
    	System.out.println("No");
    }
  }
}

Measured memory_bytes: 24232
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll; const ll MM = 1000000000;ll mod = MM + 7;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(int i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
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;}
const ll INF = 1LL << 60;

bool IsPrime(ll num){
  if (num < 2) return false;
  else if (num == 2) return true;
  else if (num % 2 == 0) return false;

  double sqrtNum = sqrt(num);
  for (ll i = 3; i <= sqrtNum; i += 2){
    if(num % i == 0) return false;
  }
  return true;
}


int main() {
  ll n; cin >> n;
  Rep(i, 1, 10) {
    Rep(j, 1, 10) {
      if (i * j == n) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}


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

const int INF  = 1e9;
const long long INFLL = 1e18;
const int NMAX = 100005;
const int MMAX = 100005;
const int KMAX = 1005;
const int MOD  = 1e9 + 7;
using namespace std;

// comment to disable debug functions
#define DEBUG

// frequently used macros

#if __cplusplus >= 201103L
#define ALL(v) begin(v),end(v)
#define SORT(v) sort(begin(v), end(v))
#define FIND(v,x) find(begin(v), end(v), (x))
#else
#define ALL(v) (v).begin(),(v).end()
#define SORT(v) sort(v.begin(), v.end())
#define FIND(v,x) find(v.begin(), v.end(), (x))
#endif

#define fi first
#define se second

#define MEMNEXT(from, to) do{ memmove((to), (from), sizeof(from)); \
memset((from), 0, sizeof(from)); } while(0)
#ifdef DEBUG
#define DUMP(x) do{ std::cerr << (#x) << ": " << x << std::endl; }while(0)
#else
#define DUMP(x) do{}while(0)
#endif

// frequent used aliases
typedef long long ll;
typedef pair<int, int> p;
typedef pair<ll, int> lp;
typedef pair<ll, ll> llp;
typedef vector<int> vec;
typedef vector<ll> vecll;
typedef vector<vec> mat;
typedef vector<vecll> matll;

// frequently used constants
static const int di[] = {-1, 0, 1, -1, 1, -1, 0, 1};
static const int dj[] = {-1, -1, -1, 0, 0, 1, 1, 1};

// frequently used structs
struct edge{
  int to,cost;
};

// printf for debug
#ifndef DEBUG
void debug(const char* format, ...){}
#else
void debug(const char* format, ...){
  va_list arg;
  va_start(arg, format);
  vprintf(format, arg);
  va_end(arg);
}
#endif

// dump vector
#ifdef DEBUG
#define DUMPV(v, c) do{       \
  printf("%s: ", #v);         \
  for (int i = 0; i < (c); ++i) \
  {                           \
  cout << (v)[i] << " ";      \
  }                           \
  cout << endl;               \
} while(0)
#else
#define DUMPV(v,c)
#endif

// std::fill of multi dimensions
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
  std::fill( (T*)array, (T*)(array+N), val );
}

// binary search
ll BSearch(ll _begin, ll _end, bool (*f)(ll)){
  ll mid;
  while(_end - _begin > 1LL) {
  mid = _begin + (_end - _begin) / 2LL;
  if(f(mid)) {
    debug("BSearch: f(%d) == true\n", mid);
    _end = mid;
  }
  else
  {
    debug("BSearch: f(%d) == false\n", mid);
    _begin = mid;
  }
  }
  return _end;
}


ll N,M,K,A,B,C,D,E;
int dp[NMAX] = {};
char dat[3][3];
string S;
vec v;

ll ans = {};

void solve(){
  // main algorithm

}
void debug(){
  // output debug information

}
void answer(){
  // output answer
  cout << dat[0][0] << dat[1][1] << dat[2][2] << endl;
}
int main(int argc, char const *argv[])
{
  // operate inputs

  // Fill(dp, -1);
  for (int i = 0; i < 3; ++i)
  {
    for (int j = 0; j < 3; ++j)
    {
      cin >> dat[i][j];
    }
  }
  solve();
  #ifdef DEBUG
  debug();
  #endif
  answer();

  return 0;
}

Measured memory_bytes: 256
// Winding

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned int UI;
typedef pair<int, int> pii;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

namespace fastIO
{
	const UI BUFFER_SIZE = (UI) 1 << 15;
	char buffer[BUFFER_SIZE], *cur, *ed;

	inline char getc() { return *(cur == ed ? ed = buffer + fread(buffer, 1, BUFFER_SIZE, stdin), cur = buffer : cur)++; }
}
using fastIO::getc;

template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getc());
	for(; !isdigit(ch); ch = getc()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getc()) sum = sum * 10 - '0' + ch;
	return sum * fg;
}

inline char *read_str(char *s)
{
	register char ch(getc());
	while(!isgraph(ch)) ch = getc();
	for(; isgraph(ch); ch = getc()) *s++ = ch;
	*s = '\0';
	return s;
}

template<typename T> inline T sqr(const T &val) { return val * val; }
template<typename T> inline int chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline int chkmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

// END tpl.

const int MOD = (int) 1e9 + 7;

const int MAXN = (int) 1e5;

int n;
char s[MAXN + 5];

inline void input()
{
	n = read_str(s + 1) - (s + 1);
}

inline void solve()
{
	static int a[MAXN + 5];

	for(int i = 1; i <= n; ++i) a[i] = s[i] == 'a' ? 1 : 2;

	int fg = 0;
	for(int i = 1; i < n; ++i) if(s[i] == s[i + 1]) { fg = 1; break; }
	if(!fg) { puts("1"); return; }

	static int sum[MAXN + 5], pos[MAXN + 5][3];

	for(int i = 1; i <= n; ++i) sum[i] = (sum[i - 1] + a[i]) % 3;
	for(int i = 0; i < 3; ++i) pos[n][i] = n + 1;
	for(int i = n - 1; i >= 0; --i)
	{
		for(int j = 0; j < 3; ++j) pos[i][j] = pos[i + 1][j];
		pos[i][sum[i + 1]] = i + 1;
	}

	static int f[MAXN + 5];

	f[0] = 1;
	for(int i = 0; i < n; ++i) if(f[i])
		for(int j = 1; j < 3; ++j)
			(f[pos[i][(sum[i] + j) % 3]] += f[i]) %= MOD;

	int ans = 0;
	for(int i = 1; i <= n; ++i) if(sum[i] == sum[n]) (ans += f[i]) %= MOD;
	printf("%d\n", ans);
}

int main()
{
#ifdef K_ON // K-ON!
	freopen("E.in", "r", stdin);
	freopen("E.out", "w", stdout);
#endif

	input();
	solve();

	return 0;
}




Measured memory_bytes: 2688
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char) 
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

fn main() {
  let (s, t): (String, String) = (read(), read());
  unsafe {
    println!("{}", if t.get_unchecked(0..s.chars().count()) == s { "Yes" } else { "No" });
  }
}

Measured memory_bytes: 2140
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <fstream>
#include <set>
#include <utility>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <numeric>
#include <sstream>
#include <list>
#include <map>

#define rep(i,p,n) for(int i=(int)p;i<(int)n;i++)
#define repp(i,p,n) for(int i=(int)p;i>=(int)n;i--)
#define Sort(x) sort(x.begin(),x.end());
#define ll long long 
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi <vector<vector<vector<int>>> 
#define vc vector<char> 
#define vvc vector<vector<char>>
#define vvvc vector<vector<vector<char>>> 

using namespace std;

int main() {
	int n, m;

	for (;;) {
		cin >> n >> m;
		if (n == 0 && m == 0) return 0;
		vector<int> v(n);
		rep(i, 0, n) cin >> v[i];
		int max = 0;
		rep(i, 0, n - 1) {
			rep(j, i + 1, n) {
				if (v[i] + v[j] <= m && v[i] + v[j] > max) {
					max = v[i] + v[j];
				}
			}
		}

		if(max!=0)cout << max << endl;
		else cout << "NONE" << endl;
	}


	return 0;
}

Measured memory_bytes: 3100
open Batteries
let n = read_int()
let rec loop i sum = 
  if i > n then sum else
  if i mod 5 = 0 || i mod 3 = 0 then loop (i+1) sum else
  loop (i+1) (sum+i)

let _ = Printf.printf "%d\n" @@ loop 1 0


Measured memory_bytes: 5244
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> Go(n), Gi(n);
	inc(i, m) {
		int s, t;
		cin >> s >> t;
		s--; t--;
		Go[s].PB(t);
		Gi[t].PB(s);
	}
	
	vector<double> P(n), E(n);
	P.back() = 1;
	dec(i, n) {
		int d = SI(Go[i]);
		if(d > 0) { P[i] /= d; E[i] /= d; }
		RF(j, Gi[i]) {
			P[j] += P[i];
			E[j] += E[i] + P[i];
		}
	}
	P.assign(n, 0);
	P.front() = 1;
	inc(i, n) {
		int d = SI(Go[i]);
		RF(j, Go[i]) { P[j] += P[i] / d; }
	}
	
	double ans = E[0];
	inc(i, n) {
		int d = SI(Go[i]);
		if(d <= 1) { continue; }
		
		double x = E[0];
		double cp = 1.0 / (d - 1) - 1.0 / d;
		double cm = 1.0 / (d - 1);
		RF(j, Go[i]) { x += cp * P[i] * E[j]; }
		RF(j, Go[i]) { setmin(ans, x - cm * P[i] * E[j]); }
	}
	
	printf("%.9f\n", ans);
	
	return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <queue>

using namespace std;
typedef long long LL;

LL ans;int n,p,a[2]; 
int main()
{
	#ifdef LOCAL_JUDGE
		freopen("biscuits.in","r",stdin);
		freopen("biscuits.out","w",stdout);
	#endif
	scanf("%d %d",&n,&p);
	for (int x,i=1;i<=n;i++)
		scanf("%d",&x),a[x&1]++;
	if (a[1]) printf("%lld",1ll<<n-1);
	else printf("%lld",p?0:1ll<<n);
	return 0;
}

Measured memory_bytes: 256
[N,M]=[int(i) for i in input().split()]
lis=[-1 for i in range(N)]
flg=0
for m in range(M):
  [s,c]=[int(i) for i in input().split()]
  if lis[s-1]==-1 or lis[s-1]==c:
    lis[s-1]=c
  else:
    flg=1
    break
x=""
if flg==1:
  print("-1")
else:
  for i in range(len(lis)):
    if i==0 and lis[i]==0 and len(lis)!=1:#先頭0排除
      print("-1")
      break
    if lis[i]==-1:#指定なし
      if flg==0 and i==0 and len(lis)!=1:
        x+="1"
        flg=2
      else:
        x+="0"
    else:#指定あり
      x+=str(lis[i])
      flg=2
    if i==len(lis)-1:print(x)

Measured memory_bytes: 38384