akhauriyash/Code-Regression huggingface dataset:
from bisect import bisect_left


def solve(string):
    a, b, q, *stx = map(int, string.split())
    s = [-10**10] + stx[:a] + [2 * 10**10]
    t = [-10**10] + stx[a:a + b] + [2 * 10**10]
    # x = dict([])
    ans = []
    i_s = 0
    i_t = 0
    for _x in stx[-q:]:
        """
        while s[i_s] < _x:
            i_s += 1
        while t[i_t] < _x:
            i_t += 1
        """
        i_s, i_t = bisect_left(s, _x), bisect_left(t, _x)
        ls, rs = s[i_s - 1], s[i_s]
        lt, rt = t[i_t - 1], t[i_t]
        r_max = max(rs, rt)
        l_min = min(ls, lt)
        """
        x[_x] = min([
            r_max - _x, _x - l_min, rt - ls + min(rt - _x, _x - ls),
            rs - lt + min(rs - _x, _x - lt)
        ])
        """
        ans.append(
            str(
                min([
                    r_max - _x, _x - l_min, rt - ls + min(rt - _x, _x - ls),
                    rs - lt + min(rs - _x, _x - lt)
                ])))
    # return "\n".join([str(x[_x]) for _x in stx[-q:]])
    return "\n".join(ans)


if __name__ == '__main__':
    n, m, l = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, l) + '\n'.join([input() for _ in range(n + m + l)])))


Measured memory_bytes: 39528
N = int(input())
l = list(map(int, input().split()))

exist_dict = {}
first_max = 0
second_max = 0

for i in l:
    if i in exist_dict:
        if exist_dict[i]==1 and i > first_max:
            second_max = first_max
            first_max = i
        elif exist_dict[i]==3 and i==first_max:
            second_max = i
        elif exist_dict[i]==1 and i > second_max:
            second_max = i
    
        exist_dict[i] = exist_dict[i] + 1
    else:
        exist_dict[i] = 1
    # print("first_max"+str(first_max))
    # print("second_max"+str(second_max))
    # print("exist_dict"+str(exist_dict))    
print(first_max*second_max)


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

long long ans[15];
const int N = 1e6 + 10;

int main()
{
    long long h, w, node[N], inf = 1e9 + 7, n, a, b, cnt = 0;
    cin >> h >> w >> n;
    for(int i = 0; i < n; i++){
        cin >> a >> b;
        for(int i = -2; i <= 0; i++){
            for(int j = -2; j <= 0; j++){
                if(a + i >= 1 && b + j >= 1 && a + i <= h - 2 && b + j <= w - 2){
                    node[cnt] = inf * (a + i) + (b + j);
                    cnt++;
                }
            }
        }
    }
    sort(node, node + cnt);
    long long tmp = 1, zero = (h - 2) * (w - 2);
    for(int i = 0; i <= cnt - 1; i++){
        if(node[i + 1] == node[i]) tmp++;
        else{
            ans[tmp]++;
            tmp = 1;
            zero--;
        }
    }
    cout << zero << endl;
    for(int i = 1; i <= 9; i++) cout << ans[i] << endl;
}

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

namespace AtCoders {
	class Program {
		static void Main(string[] args) {

			var inputArray = retreiveLongArray();
			var inputCount = 3;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			var a = inputArray[0];
			var b = inputArray[1];
			var c = inputArray[2];

			var ans = getAnswer(a, b, c) ? "Yes" : "No";
			Console.WriteLine(ans);

		}

		/// <summary>
		/// 第1の解放
		/// </summary>
		/// <param name="a"></param>
		/// <param name="b"></param>
		/// <param name="c"></param>
		/// <returns></returns>
		private static bool getAnswer(long a,long b, long c) {


			if(c-a-b <= 0) {
				return false;
			}
			var l = (ulong)(c - a - b);
			var left = l*l;
			var right = (ulong) (4 * a * b);
			if (left > right) {
				return true;
			}
			else {
				return false;
			}

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=100005;
int x[MAX_N];
int n,A,B; 
int main()
{
	cin>>n>>A>>B;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];
	}
	LL ans=0;
	for(int i=1;i<n;i++)
	{
		ans+=min((LL)A*(x[i+1]-x[i]),(LL)B);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
S=str(input())
l=len(S)
flag=0
if S==S[::-1]:
    s1=S[0:(l-1)//2]
    s2=S[(l+1)//2:]
    if s1==s1[::-1] and s2==s2[::-1]:
        flag=1

if flag==1:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int c = Integer.parseInt(sc.next());
		
		int five=0;
		int seven=0;
		
		if(a==5) {
			five++;
		}else {
			seven++;
		}
		
		if(b==5) {
			five++;
		}else {
			seven++;
		}
		
		if(c==5) {
			five++;
		}else {
			seven++;
		}

		if(five==2 && seven==1) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}		
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e15)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define arrdump(n,a) for(int i=0;i<n;i++) {cout<<((i>0)? " ":"")<<a[i];}cout<<"\n";


typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://atcoder.jp/contests/abc042/tasks/abc042_a

int main() {
    int a[3];
    REP(i, 3) {
        cin >> a[i];
    }
    sort(a, a+3);
    if (a[0]==5&&a[1]==5&&a[2]==7) {
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }

    return 0;
}

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

using namespace std;

typedef long long ll;
// constexpr ll MOD = 998244353;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

//     int root(int x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//     }

//     bool same(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };

int main(void) {
    int H, W;
    vector<string> S(60);
    cin >> H >> W;
    for (int i=0;i<H;i++) cin >> S[i];
    for (int i=0;i<H;i++) for (int j=0;j<W;j++) {
        if (S[i][j] == '.') continue;
        // cout << i << "," << j << endl;
        bool flag = false;
        if (i>0) if (S[i-1][j] == '#') flag |= true;
        if (j>0) if (S[i][j-1] == '#') flag |= true;
        if (i<H-1) if (S[i+1][j] == '#') flag |= true;
        if (j<W-1) if (S[i][j+1] == '#') flag |= true;
        if (!flag) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
protocol InitFromString {
    init?(_ str: String)
}

extension Int: InitFromString {}
extension Int8: InitFromString {}
extension Int16: InitFromString {}
extension Int32: InitFromString {}
extension Int64: InitFromString {}
extension String: InitFromString {}

func input<T: InitFromString>() -> [T] {
    readLine()!.split(separator: " ").map(String.init).compactMap(T.init)
}

func fx(x: Int, y: Int, z: Int) -> Int {
    x * x +  y * y + z * z + x * y + y * z +  z * x
}

let n: Int = input()[0]

import Foundation
var scores = (0..<n).map { _ in 0 }

(1...Int(sqrt(Double(n)))).forEach { (i) in
    (1...Int(sqrt(Double(n)))).forEach { (j) in
        (1...Int(sqrt(Double(n)))).forEach { (k) in
            let result = fx(x: i, y: j, z: k)
            guard result <= n else {
                return
            }
            scores[result - 1] += 1
        }
    }
}
scores.forEach {
    print($0)
}



Measured memory_bytes: 13136
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

const int L=1e5+10;
vector<int> es[L];
int m;
int f(int r,int p) {
	vector<int> len;
	for(int i:es[r]){
		if(i==p)continue;
		int v=f(i,r);
		if(v>m){
			return m+1;
		}
		len.push_back(v);
	}
	if(len.size()%2==0){
		len.push_back(0);
	}
	sort(len.begin(),len.end());
	int low=-1;
	int hi=len.size();
	while(low+1<hi){
		int c=(low+hi)/2;
		int h=0;
		int t=len.size()-1;
		if(h==c)h++;
		if(t==c)t--;
		bool ok=true;
		while(h<t){
			if(len[h]+len[t]>m){
				ok=false;
				break;
			}
			h++;
			t--;
			if(h==c)h++;
			if(t==c)t--;
		}
		if(ok){
			hi=c;
		}
		else{
			low=c;
		}
	}
	if(hi<len.size()){
		//cerr << m << ", " << r << ", " << p << ", " << len[hi]+1 << endl;
		return len[hi]+1;
	}
	return m+1;
}
int main() {
	int N;
	cin >> N;
	for(int i=0;i<N-1;i++){
		int a,b;
		cin >> a >> b;
		es[a].push_back(b);
		es[b].push_back(a);
	}
	int c=0;
	int s=0;
	for(int i=1;i<=N;i++){
		c+=es[i].size()%2;
		if(es[i].size()==1){
			s=i;
		}
	}

	int low=0,hi=N-1;
	while(low+1<hi){
		m=(low+hi)/2;
		//cerr << low << ", " << hi << ", " << m << ": " << f(s,0) << endl;
		if(f(es[s][0],s)<=m){
			hi=m;
		}
		else{
			low=m;
		}
	}
	cout << c/2 << " " << hi << endl;

	return 0;
}



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

int n, m;
int chk[100001];
struct edg {
    int idx, dst;
};
vector<edg> gph[100001];
int dst[100001];

void go(int now, int cnt) {
    dst[now] = cnt;
    chk[now] = 1;
    for (edg nxt : gph[now]) {
        if (!chk[nxt.idx]) {
            go(nxt.idx, cnt+nxt.dst);
        }
        else {
            if (dst[nxt.idx] != cnt+nxt.dst) {
                puts("No");
                exit(0);
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    while (m--) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        gph[u].push_back({ v,w });
        gph[v].push_back({ u,-w });
    }

    for (int i = 1; i <= n; i++) {
        if (!chk[i]) {
            go(i, 0);
        }
    }

    puts("Yes");

    return 0;
}

Measured memory_bytes: 11392
def has_keyence(S):
    if S.startswith('keyence'):
        return 'YES'
    elif S.endswith('keyence'):
        return 'YES'
    else:
        check = [['k', 'eyence'],
                 ['ke', 'yence'],
                 ['key', 'ence'],
                 ['keye', 'nce'],
                 ['keyen', 'ce'],
                 ['keyenc', 'e']]
        for c in check:
            if S.startswith(c[0]) and S.endswith(c[1]):
                return 'YES'
    return 'NO'

S = input()
print(has_keyence(S))


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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N,x,y; cin>>N>>x>>y;
  vector<vector<ll>> G(N);
  G.at(0)={1};
  G.at(N-1)={N-2};
  for(ll i=1;i<N-1;i++){
    G.at(i)={i-1,i+1};
  }
  G.at(x-1).push_back(y-1);
  G.at(y-1).push_back(x-1);
  vector<ll> L(N+1);
  
  for(ll k=0;k<N;k++){
    // BFS のためのデータ構造
    vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
    queue<int> que;

    // 初期条件 (頂点 k を初期ノードとする)
    dist[k] = 0;
    que.push(k); // k を橙色頂点にする

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }


    // 結果出力 (各頂点の頂点 0 からの距離を見る)
    for (int v = 0; v < N; ++v) L.at(dist[v])++;
}
   for (int v = 1; v < N; ++v) cout<<L.at(v)/2<<endl;
}
  


Measured memory_bytes: 384
# -*- coding: utf-8 -*-
N = input()
A = map(int, input().split())
A = list(A)
count = 0
flag = True

while flag:
    l = []
    for element in A:
        if element%2 == 1:
            flag = False
            count -= 1
            break
        l.append(element/2)
    A = l
    count += 1

print(count)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mk make_pair
#define rint register int
#define debug(x) cerr<<#x<<" "<<x<<"\n"; 
using namespace std;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return w*s;}
ll L,N,X[1010000],ans,Sum1[1000010],Sum2[1000010],Summ1[1000010],Summ2[1000010];
inline ll Solve(int pos,int dir)
{
	ll res=0;
//	debug(pos)
//	debug(dir) 
	if(dir)
	{
		res=Sum2[N-pos+1]<<1;
		
		int Midpt=(N-pos+1)/2;
//		debug(Midpt)
		res+=2*Summ1[Midpt];
		res+=2*(Summ2[Midpt+1]-Summ2[N-pos+1]);
//		debug(res)
		if((N-pos)%2==0) res-=Sum2[Midpt+1];
		else res-=Sum1[Midpt];
	}
	else 
	{
		res=Sum1[pos]<<1;
		int Midpt=(N-(N-pos+1)/2+1);
//		debug(Midpt)
		res+=2*Summ2[Midpt];
		res+=2*(Summ1[Midpt-1]-Summ1[pos]);
		if((N-pos)%2==0) res-=Sum1[Midpt-1];
		else res-=Sum2[Midpt];
	}
//	debug(res)
	return res;
}
int main()
{
	L=read(),N=read();
	for(rint i=1;i<=N;++i) X[i]=read();
	for(rint i=1;i<=N;++i)
	{
		Sum1[i]=X[i];
		Summ1[i]=Sum1[i]+Summ1[i-1];
	}X[N+1]=L;
	for(rint i=N;i>=1;--i)
	{
		Sum2[i]=L-X[i];
		Summ2[i]=Sum2[i]+Summ2[i+1];
	}
	for(rint i=1;i<N;++i)
	{
		ans=max(ans,Solve(i,0));ans=max(ans,Solve(i,1));
	}ans=max(ans,max(Sum1[N],Sum2[1]));
	cout<<ans;
	return 0;
}


Measured memory_bytes: 18176
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
ll x,k,d;
ll ans;
cin>>x>>k>>d;
x=abs(x);
if(x/d>k)
{
ans=x-k*d;
}

else
{
k=k-x/d;
x=x-d*(x/d);

if(k%2==1)ans=abs(x-d);
else ans=x;


}

cout <<ans;
}

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

// Aliases
#define enable_fast_io()  	ios_base::sync_with_stdio(false); 	\
			  				cin.tie(nullptr); 					\
							cout.tie(nullptr)  

#define N 300010LL
#define round(n) int64_t(n+0.5)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef pair<int,int> pi;

int main(){
	enable_fast_io();

	int a;
	cin >> a;

	cout << (a + (a*a) + (a*a*a)) << "\n";
	
	return 0;
}

Measured memory_bytes: 3576
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>


using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<n;++i)
#define FOR(i, a, b) for(int i=a;i<b;++i)
#define RREP(i, n) for(int i=n-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=b-1;i>=a;--i)

#define all(x) begin(x),end(x)
#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

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


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> p) {
    os << p.first << ":" << p.second;
    return os;
}

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

template<class T1, class T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "[";
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        if (it != mp.begin()) {
            os << ", ";
        }
        os << *it;
    }
    return os << "]";
}

// edit

void solve() {
    char c;
    cin >> c;

    if (c >= 'a' && c <= 'z') {
        cout << "a" << endl;
    } else {
        cout << "A" << endl;
    }


}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());

    solve();


    return 0;
}


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

int main(){
    int n,m,c; cin >> n >> m >> c;
    vector<int> b(m);
    rep(i,m) cin >> b[i];
    vector<vector<int>> code(n,vector<int>(m));
    rep(i,n) rep(j,m) cin >> code[i][j];
    
    int sum = 0;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            sum += b[j] * code[i][j];
        }
        if(sum + c > 0) cnt++;
        sum = 0;
    }
    cout << cnt;
}

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

int main()
{
	string S;
	cin >> S;
	int n = S.size();
	int res = 1e5;
	for (int i = 0; i + 3 <= n; i++) {
		res = min(res, abs(753 - stoi(S.substr(i, 3))));
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	private Scanner sc;

	int[][] map;
	public static void main(String[] args) {
		new Main();
	}
	
	public Main() {
		sc = new Scanner(System.in);
		
		int sets = Integer.parseInt(sc.nextLine());
		
		for (int index = 0; index < sets; index++) {
			sc.nextLine();
			
			map = new int[8][8];
			for (int i = 0; i < map.length; i++) {
				String line = sc.nextLine();
				for (int j = 0; j < map.length; j++) {
					map[j][i] = line.charAt(j) - '0';
				}
			}
			
			LinkedList<Integer[]> boms = new LinkedList<Integer[]>();
			Integer[] xy = new Integer[2];
			xy[0] = Integer.parseInt(sc.nextLine()) - 1;
			xy[1] = Integer.parseInt(sc.nextLine()) - 1;
			if (map[xy[0]][xy[1]] == 1) {
				map[xy[0]][xy[1]] = 0;
				boms.add(xy);
			}
			
			while (boms.isEmpty() == false) {
				xy = boms.pop();
				
				int tx = xy[0];
				int ty = xy[1];
				
				
				for (int i = -3; i < 4; i++) {
					if ((tx + i) < 0) continue;
					if ((tx + i) > 7) break;
					
					if (map[tx + i][ty] == 1) {
						map[tx + i][ty] = 0;
						
						Integer[] nxy = new Integer[2];
						nxy[0] = tx + i;
						nxy[1] = ty;
						boms.add(nxy);
					}
				}

				for (int i = -3; i < 4; i++) {
					if ((ty + i) < 0) continue;
					if ((ty + i) > 7) break;	
					
					if (map[tx][ty + i] == 1) {
						map[tx][ty + i] = 0;
						
						Integer[] nxy = new Integer[2];
						nxy[0] = tx;
						nxy[1] = ty + i;
						boms.add(nxy);
					}
				}
			}
			
			System.out.println("Data " + (index + 1) + ":");
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map.length; j++) {
					System.out.print(map[j][i]);
				}
				System.out.println();
			}
		}
	}
}

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

int main() {
    int N, K; cin >> N >> K;
    string S; cin >> S;

    // 「1 の個数」「0 の個数」を交互に記録していく
    vector<int> nums;    
    if (S[0] == '0') nums.push_back(0); // 先頭が 0 だったら
    for (int i = 0; i < S.size();) {
        int j = i;
        while (j < S.size() && S[j] == S[i]) ++j; // S[i] の数値がどこまで続くか
        nums.push_back(j - i);
        i = j;
    }
    if (S.back() == '0') nums.push_back(0); // 最後尾が 0 だったら

    // 累積和
    vector<int> sums((int)nums.size() + 1, 0);
    for (int i = 0; i < nums.size(); ++i) sums[i+1] = sums[i] + nums[i];

    // 偶数番目の添字から始まる、長さ 2K+1 (以下) の区間の総和のうち、最大値を求める
    int res = 0;
    for (int left = 0; left < sums.size(); left += 2) {
        int right = left + K*2+1;
        if (right >= sums.size()) right = (int)sums.size() - 1;
        res = max(res, sums[right] - sums[left]);
    }
    cout << res << endl;
}

Measured memory_bytes: 1400
N=int(input())
A=sorted(int(input())for _ in [0]*N)
n=N//2;m=n+1
print(2*sum(A[n+1:])-2*sum(A[:n-1])+A[n]-A[n-1]-(min(A[n-1]+A[n+1],2*A[n])if N%2>0 else 0))

Measured memory_bytes: 7852
#include "iostream"
#include "string"
#include "vector"

using namespace std;

const int MOD=1000000007;

int main(){
	string s,t;
	cin>>s>>t;
	int N=s.size();
	int M=t.size();
	s='a'+s;
	t='a'+t;
	vector<vector<int> >dp(N+1,vector<int>(M+1));
	dp[0][0]=1;
	for(int i=1;i<=N;i++){
		dp[i][0]=dp[i-1][0];
		for(int j=1;j<=M;j++){
			if(s[i]==t[j]){
				dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
				dp[i][j]%=MOD;
			}
			else{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	cout<<dp[N][M]<<endl;
}


Measured memory_bytes: 6908
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
using ll = long long;

int main()
{
	string S;
	cin >> S;
	int sum1 = 0;
	int sum2 = 0;
	for (size_t i = 0; i < S.size(); ++i) {
		if (S[i] == '0') {
			sum1++;
		}
		else {
			sum2++;
		}
	}
	cout << S.size() - abs(sum1 - sum2) << endl;
	return 0;
}



Measured memory_bytes: 512
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdlib>
using namespace std;

int main()
{
  int n,p;
  cin >> n >> p;
  cout << (3*n+p)/2 << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif
 
//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
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 (a > b) { a = b; return true; } return false; }
 
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, T; cin >> N >> T;
    vector<int>v(T + 1, 0);
    rep(i, 0, N) {
        int l, r; cin >> l >> r;
        v[l]++; v[r]--;
    }
    rep(i, 1, T+1)v[i] += v[i - 1];
    cout << *max_element(all(v)) << endl;
    return 0;
}

Measured memory_bytes: 3332
#include<bits/stdc++.h>
using namespace std;
long long ans[100];
long long dfs(long long n)
{
	if(ans[n])return ans[n];
	if(n==0)return ans[n]=2;
	if(n==1)return ans[n]=1;
	return ans[n]=dfs(n-1)+dfs(n-2);
}
long long n;
int main()
{
	cin>>n;
	cout<<dfs(n)<<endl;
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O2")
#include<iostream>
using namespace std;
#define f(x,y,z) for(int x=y;x<z;++x)
int h, h1, h2, n, c, l, r, t, z;
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    f(i,1,n+1) {
        h = h1 = h2 = 0;
        for(int x = 1; x*x+x+x+2 < i; ++x) {
            for(int y = x; x*x+y*y+x*y+x+y < i; ++y) {
                z = y;
                while(x*x+y*y+z*z+x*y+y*z+z*x < i) ++z;
                if(x*x+y*y+z*z+x*y+y*z+z*x == i) {
                    if(x == y || y == z || z == x) {
                        if(x == y && y == z && z == x) ++h2;
                        else ++h1;
                    } else ++h;
                }
            }
        }
        cout << h*6+h1*3+h2 << '\n';
    }
    // cout << c << '\n';
}

Measured memory_bytes: 3600
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>

#define rep(i,n) for(int i=0;i<(n);i++)
#define EPS (1e-7)
#define INF (2e9)

using namespace std;
typedef long long int ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef priority_queue<int> PQI;
typedef priority_queue<int,vector<int>,greater<int> > PQSI;
typedef priority_queue<ll> PQL;
typedef priority_queue<ll,vector<ll>,greater<ll> > PQSL;

const int MOD = 1000000007;
struct mint { int n; mint(int n_ = 0) : n(n_) {} };
mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

vector<mint> F_{1, 1}, R_{1, 1}, I_{0, 1};
void check_fact(int n) {
  for (int i = I_.size(); i <= n; i++) {
    I_.push_back(I_[MOD % i] * (MOD - MOD / i));
    F_.push_back(F_[i - 1] * i);
    R_.push_back(R_[i - 1] * I_[i]);
  }
}

mint I(int n) { check_fact(abs(n)); return n >= 0 ? I_[n] : -I_[n]; }
mint F(int n) { check_fact(n); return n < 0 ? 0 : F_[n]; }
mint R(int n) { check_fact(n); return n < 0 ? 0 : R_[n]; }
mint C(int n, int r) { return F(n) * R(n - r) * R(r); }
mint P(int n, int r) { return F(n) * R(n - r); }
mint H(int n, int r) { return n == 0 ? (r == 0) : C(n + r - 1, r); }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T>
T gcd(T x, T y){
    if (y == 0) return x;
    else return gcd(y, x % y);
}

template<typename T>
T lcm(T x, T y){
    return (x / gcd(x, y)) * y;
}

int N, M;
int dp[100001];
vector<int> G[100001];

int dps(int v){
    if(dp[v] != -1) return dp[v];

    int a = 0;
    for(auto e:G[v]) chmax(a,dps(e)+1);
    return dp[v] = a;
}

int main(void){
    cin >> N >> M;
    rep(i,M){
        int x, y;
        scanf("%d%d",&x,&y);
        G[x-1].push_back(y-1);
    }

    rep(i, N) dp[i] = -1;
    rep(i,N) dps(i);
    int a;
    rep(i,N) chmax(a, dp[i]);

    cout << a << endl;

    return 0;
}



Measured memory_bytes: 8192
using System;
using System.Collections.Generic;
using System.Linq;

static class APointInATriangle
{
    static void Main()
    {
        Func<double, double, double> dist = (a, b) => b - a;
        var q =
            from input in
                Enumerable.Repeat<Func<string>>( Console.ReadLine, 100 )
                    .Select( x => x() )
                    .TakeWhile( x => x != null )
                    .Select( x => x.Split( ' ' ).Select( double.Parse ) )
            let points = input
                .Select( (x, i) => new { v = x, k = i >> 1 } )
                .GroupBy( x => x.k, x => x.v )
                .ToArray()
            select
                points.Take( 3 )
                .Aggregate( 
                    new { v = points[2], s = new List<double>() },
                    (x, y) => {
                        var e = y.Zip( x.v, dist ).ToArray();
                        var p = y.Zip( points[3], dist ).ToArray();
                        x.s.Add( e[0] * p[1] - e[1] * p[0] );
                        return new { v = y, s = x.s };
                        },
                    x => x.s )
                .Aggregate( 
                    new { n = true, p = true },
                    (x, y) => new { n = x.n && y < 0, p = x.p && y > 0 },
                    x => x.n || x.p ? "YES" : "NO" );
        q.ToList().ForEach( Console.WriteLine );
    }

    static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(
        this IEnumerable<TFirst> first,
        IEnumerable<TSecond> second,
        Func<TFirst, TSecond, TResult> func )
    {
        var f = new Queue<TFirst>( first );
        var s = new Queue<TSecond>( second );
        while ( f.Any() && s.Any() )
            yield return func( f.Dequeue(), s.Dequeue() );
    }
}

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

const int MAX = 100005;
int a[MAX];
int main() {
	// freopen("a.in", "r", stdin);
	int n; scanf("%d", &n);
	int maxabs = -1; int id = 0;
	for (int i=1; i<=n; i++) { 
		scanf("%d", &a[i]); 
		if (abs(a[i]) > maxabs) { maxabs = abs(a[i]); id = i; }
	}
	vector<int> x, y;
	for (int i=1; i<=n; i++) {
		x.push_back(id); y.push_back(i);
		a[i] += a[id];
	}
	if (maxabs == 0) { printf("0\n"); return 0; }
	if (a[1] < 0) {
		for (int i=n; i>=2; i--) {
			x.push_back(i); y.push_back(i-1);
		}
	}
	else {
		for (int i=1; i<n; i++) {
			x.push_back(i); y.push_back(i+1);
		}
	}
	printf("%d\n", (int)x.size());
	for (int i=0; i<x.size(); i++) {
		printf("%d %d\n", x[i], y[i]);
	}
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
using namespace std;

namespace adaptor = boost::adaptors;

void Main()
{
	int K, X;
    cin >> K >> X;

    if(K*500 >= X) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	
	Main();
}

Measured memory_bytes: 256
sx, sy, tx, ty=map(int, input().split())
print("D"+"R"*(tx-sx+1)+"U"*(ty-sy+1)+"L"*(tx-sx+1)+"D"*(ty-sy)+
      "L"+"U"*(ty-sy+1)+"R"*(tx-sx+1)+"D"*(ty-sy+1)+"L"*(tx-sx))

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

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

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

  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h.at(i);
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (h.at(i) >= k) ans++;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int  long long int
#define mod 1000000007
#define b1(n) __builtin_popcount(n)
vector<int>sie; 
 inline int gEd(int a, int b, int *ax, int *ay) 
{ 
	int x,y;  
	if (a==0) 
	{   *ax=0;
		*ay = 1; 
		return b;
	}
    int g = gEd(b%a,a,&x,&y);
    *ax=y-(b/a)*x; 
	*ay=x; 
	return g; 
}  
inline int mli(int a,int m) //mli(a,m)
{
	int ax,ay;
	     gEd(a,m,&ax,&ay);
	    int val1=(ax%m+m)%m; 
	    return val1;
}
inline int powerm(int a,int n)   //powerm(a,n)
{
	int ans=1;
	while(n>0)
	{
		int last_bit=(n&1);
		if(last_bit)
		ans=((ans%mod)*(a%mod))%mod;
		a=((a%mod)*(a%mod))%mod;
		n=n>>1;
	}
	return ans;
}
inline int power(int a,int n)   //power(a,n)
{
	int ans=1;
	while(n>0)
	{
		int last_bit=(n&1);
		if(last_bit)
		ans=ans*a;
		a=a*a;
		n=n>>1;
	}
	return ans;
}
inline int add(int a,int b)
{
	int s=((a%mod)+(b%mod))%mod;
	return s;
}
inline int sub(int a,int b)
{
	int s=((a%mod)-(b%mod))%mod;
	return s;
}
inline int mul(int a,int b)
{
	int s=((a%mod)*(b%mod))%mod;
	return s;
}
inline int ncr(int n, int k)  //ncr(a,b)
{ 
    int res = 1; 
  
 
    if (k > n - k) 
        k = n - k; 
  
  
    for (int i = 0; i < k; ++i) { 
        res *= (n - i); 
        res /= (i + 1); 
    } 
  
    return res; 
} 
inline void sieve()   //sieve vector->sie
{
	const int n=10000000;
	bitset<10000000>b;
	b.set();
	b[0]=b[1]=0;
	for(int i =2;i<=n;i++)
	{
		if(b[i])
		{
			sie.push_back(i);
			for(int j=i*i;j<=n;j=j+i)
			b[j]=0;
		}
	}
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     string s;
     cin>>s;
   if(s=="SUN"){
	   cout<<"7"<<endl;
	   }
   if(s=="MON"){
	   cout<<"6"<<endl;
	   }
   if(s=="TUE"){cout<<"5"<<endl;}
   if(s=="WED"){cout<<"4"<<endl;}
   if(s=="THU"){cout<<"3"<<endl;}
   if(s=="FRI"){cout<<"2"<<endl;}
   if(s=="SAT"){cout<<"1"<<endl;}
    
		
		
		
    
    
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define rep(i,n)  for(ll i=0; i<n; i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF 1e9
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
  vi x(5); rep(i,5) cin >> x[i];
  rep(i,5) if(x[i]==0) cout << i+1;
}


Measured memory_bytes: 3620
import Text.Printf

main = do
    ss <- getLine
    let (a:b:c:_) = map (\x -> read x :: Double) $ words ss
    let s = area a b c
    let l = circumference a b c
    let h = height a b c
    printf "%.8f\n" s
    printf "%.8f\n" l
    printf "%.8f\n" h

area a b c = (1/2) * a * b * (sin $ c * pi / 180)
left a b c = sqrt $ a^2 + b^2 - 2 * a * b * (cos $ c * pi / 180)
circumference a b c = a + b + (left a b c)
height a b c = (area a b c) * 2 / a



Measured memory_bytes: 4172
#include <iostream>
#define mod 1000000007

using namespace std;
long long cs,s,i,ans;
long long fact[2005];
long long inv[2005];
long long put(long long baza, long long exp)
{
    if(exp==0)
        return 1;

    long long ans=put(baza, exp/2);
    ans*=ans;
    ans%=mod;

    if(exp%2)
    {
        ans*=baza;
        ans%=mod;
    }

    return ans;
}
void genfact()
{
    fact[0]=1;
    for(long long i=1;i<=s;i++)
        fact[i]=(fact[i-1]*i)%mod;

    inv[s]=put(fact[s], mod-2);
    for(long long i=s-1;i>=0;i--)
        inv[i]=(inv[i+1]*(i+1))%mod;
}
long long comb(long long k, long long n)
{
    long long ans=fact[n]*inv[n-k];
    ans%=mod;
    ans*=inv[k];
    ans%=mod;

    return ans;
}
long long cr(long long cutii,long long bomboane)
{
    return comb(cutii-1, cutii+bomboane-1);
}
int main()
{
    cin>>s;
    genfact();

    for(i=1;3*i<=s;i++)
    {
        cs=s-3*i;

        ans+=cr(i, cs);
        ans%=mod;
    }

    cout<<ans;
    return 0;
}


Measured memory_bytes: 3588
using System;
using System.Collections.Generic;

namespace AGC039_B___Graph_Partition
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(solve());
        }
        static int solve()
        {
            var N = int.Parse(Console.ReadLine());
            var connection = new int[N + 1, N + 1];
            for (int i = 0; i < N; i++)
            {
                var read = Console.ReadLine();
                for (int j = 0; j < N; j++)
                {
                    connection[i + 1, j + 1] = read[j] == '0' ? int.MaxValue : 1;
                    if (i == j) connection[i + 1, j + 1] = 0;
                }
            }

            var partition = new int[N + 1];
            partition[1] = 1;
            var queue = new Queue<int>();
            queue.Enqueue(1);
            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                for (int next = 1; next < N + 1; next++)
                {
                    if (connection[current, next] != 1) continue;
                    if (partition[current] == partition[next]) return -1;
                    if (partition[next] == 0)
                    {
                        partition[next] = -partition[current];
                        queue.Enqueue(next);
                    }
                }
            }

            for (int via = 1; via < N + 1; via++)
            {
                for (int from = 1; from < N + 1; from++)
                {
                    for (int to = 1; to < N + 1; to++)
                    {
                        if (connection[from, via] == int.MaxValue || connection[via, to] == int.MaxValue) continue;
                        connection[from, to] = Math.Min(connection[from, to], connection[from, via] + connection[via, to]);
                    }
                }
            }

            var max = 0;
            for (int i = 1; i < N + 1; i++) for (int j = 1; j < N + 1; j++) max = Math.Max(max, connection[i, j]);
            return max + 1;
        }
    }
}


Measured memory_bytes: 13360
import java.util.Scanner

/**
 * Created by sonetsuyoshi on 2015/12/16.
 */
object Main extends App {
  val sc = new Scanner(System.in)

  val N = sc.nextLong
  val A = sc.nextLong


  var minTime = N

  for(eatCount <- 1 to 40) {
    val time1 = math.pow(N, 1.0 / (eatCount + 1)).toLong
    val time2 = (time1 + 1).toLong

    var countTime1 = eatCount + 1
    var countTime2 = 0
    while(math.pow(time1, countTime1) * math.pow(time2, countTime2) < N) {
      countTime1 -= 1
      countTime2 += 1
    }

    val newTime = time1 * countTime1 + time2 * countTime2 + eatCount * A
    minTime = math.min(minTime, newTime)
  }

  println(minTime)
}

Measured memory_bytes: 22464
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

#define mem(dp,a)           memset(dp,a,sizeof dp)
#define rep(i,a,b)          for(ll i=a;i<b;i++)
#define pb(x)               push_back(x)
#define mp(x,y)             make_pair(x,y)
#define fastio              ios_base::sync_with_stdio(false);cin.tie(NULL)
#define F                   first
#define S                   second
#define all(v)              (v).begin(),(v).end()
#define pi					3.14159265359
ll INF=1e18+10;
ll MOD=1000000007;

int main()
{
    int n;cin>>n;
    ll f[1010];mem(f,0);
    rep(i,0,n)
    {
        ll a;cin>>a;
        f[a]++;
    }
    ll pref[2010];mem(pref,0);
    rep(i,0,1010)
    pref[i]=f[i];
    rep(i,2,2010)
    pref[i]+=pref[i-1];

    ll ans=0;


    rep(i,1,1001)
    {
        rep(j,1,i+1)
        {
            if(i!=j)
                ans+=((pref[i+j-1]-pref[i])*f[i]*f[j]);
            else
            {
                //ans+=((pref[i+j-1]-pref[i])*((f[i]*(f[i]-1))/2));
                ans+=((f[i]*(f[i]-1)*(f[i]-2))/6);
                ans+=((pref[2*i-1]-f[i])*((f[i]*(f[i]-1))/2));
            }
        }
    }
    cout<<ans;
}


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

int main()
{
	int n;
	string s;
	
	cin >> n;
	for( int i = 0; i < n; i++ ){
		cin >> s;
		int digitNum = s.length();
		int digitSum = 0;
		for( int j = 0; j < digitNum; j++ ){
			digitSum += s[j] - '0';
		}
		int turnNum = (digitSum - 1) / 9 + digitNum - 1;
		if( turnNum % 2 ){
			cout << "Fabre wins." << endl;
		}
		else{
			cout << "Audrey wins." << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1196
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

void solve() {
  int r, w, c, dr;
  while (cin >> r >> w >> c >> dr, r) {
    int x = 0;
    for (;;) {
      if (r >= c * w) {
        cout << x << endl;
        break;
      }
      x++;
      r += dr;
    }
  }
}

Measured memory_bytes: 3080
#include <stdio.h>
int main(void){
    int room[4][3][10]={{{0}}};
    int n,b,f,r,v;
    int i,j,k;
    
    scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%d %d %d %d",&b,&f,&r,&v);
        room[b-1][f-1][r-1] += v;
    }
    
    for(i=0; i<3; i++){
        for(j=0; j<3; j++){
            for(k=0; k<10; k++){
                printf(" %d",room[i][j][k]);
                
            }
            putchar('\n');
        }
    
        puts("####################");
    }
    
    for(j=0; j<3; j++){
        for(k=0; k<10; k++){
            printf(" %d",room[3][j][k]);
        }
        putchar('\n');    
    }
    return 0;
}

Measured memory_bytes: 612
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
using namespace std::chrono;
long long int p=1e9 +7;
ll n,k;
ll seq[105];
bool debugging=0;
bool outputcheck=0;
bool timecheck=0;
void init(){
    if(debugging){
        
    }
    else{
        cin>>n>>k;
        for(int i=0;i<n;i++){
            cin>>seq[i];
        }
    }
}
long long int modpower(ll b,ll po, ll mod=p){
    long long int ans=1;
    while(po){
        if(po&1){
            ans*=b;
            ans%=mod;
        }
        b*=b;
        b%=mod;
        po>>=1;
    }
    return ans;
}
ll solve(){
    ll ans[n+1][k+1];
    ll sum[n+1][k+2];
   for(int i=0;i<=n;i++){
       for(int j=0;j<=k;j++){
           ans[i][j]=0;
           sum[i][j]=0;
       }
       sum[i][k+1]=0;
   }
   ans[0][0]=1;
   for(int i=1;i<=k+1;i++){
       sum[0][i]=1;
   }
   for(int i=1;i<=n;i++){
       for(ll j=0;j<=k;j++){
           ans[i][j]=sum[i-1][j+1]-sum[i-1][max(0ll,j-seq[i-1])];
           ans[i][j]%=p;
       }
       for(int j=1;j<=k+1;j++){
           sum[i][j]=sum[i][j-1]+ans[i][j-1];
           sum[i][j]%=p;
       }
   }
   /*
   for(int i=0;i<=n;i++){
       for(int j=0;j<k+1;j++){
           cout<<ans[i][j]<<" ";
       }
       cout<<"\n";
   }
    for(int i=0;i<=n;i++){
       for(int j=0;j<=k+1;j++){
           cout<<sum[i][j]<<" ";
       }
       cout<<"\n";
   }
   */
   return (ans[n][k]%p + p)%p;
}
ll solvebad(){

}
int output(){
   
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	//cin >>t;
	t=1;
    srand(time(0));
	while(t--){
	   init();
	   if(debugging){
	       if(outputcheck){
	          if(solve()!=solvebad()){//checking for random input
	             output();
	          }
	       }
	       if(timecheck){
	           auto start=high_resolution_clock::now();
	           solve();
	           auto stop=high_resolution_clock::now();
	           auto duration = duration_cast<microseconds>(stop - start);
	           cout<<duration.count()<<" Fast\n";
	           start=high_resolution_clock::now();
	           solvebad();
	           stop=high_resolution_clock::now();
	           duration = duration_cast<microseconds>(stop - start);
	           cout<<duration.count()<<" Slow\n";
	       }
	   }
	   else{
	       cout<<solve()<<"\n";//solving it correctly
	   }
	}
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++) 
#define ll long long
#define ld long double
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)  
#define outdeb(fir, sec, thr) cout << fir << ":" << sec << ":" << thr << endl

int main()
{
  int n,m;
  cin >> n >> m;
  vector<set<int>> r;
  vector<ll> h;
  rep(i, n)
  {
    int t;
    cin >> t;
    h.push_back(t);
    r.push_back(set<int>());
  }
  rep(i, m)
  {
    int a, b;
    cin >> a >> b;
    r[a-1].insert(b-1);
    r[b-1].insert(a-1);
  }
  ll ans = 0;
  rep(i, n)
  {
    bool isError = false;
    for(auto iter = r[i].begin(); iter != r[i].end(); iter++)
    {
      int z = *iter;
      if(h[i] <= h[z])
      {
        isError = true;
        break;
      }
    }
    if(!isError)
    {
      ans++;
    }
  }
  
  cout << fixed << ans << endl;
  return 0;
}

Measured memory_bytes: 17996
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define si size()
#define bk back()
#define popb pop_back()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define emp empty()
#define beg begin()
#define en end()
#define ump unordered_map
#define forl(i,a,n) for(int i=a;i<n;i++)
#define rfor(i,n,a) for(int i=n;i>=a;i--)
#define fore(i,a,n) for(int i=a;i<=n;i++)
#define len length()
const int N=1e9+7;

// dp[i][j] means we are at position i and total sum in knapsack is j
// so aat position i we can take the element i or leave it
// if we take it the transiotio nto dp[i][j]--->dp[i-1][j-weight[i]] other wise dp[i][j]-->dp[i-1][j]
//iterative approach   time-O(n*W)  space-O(n*W)


//Note at given (i,j) we only need to store the value in previous row i.e (i-1,j)
//This observation can reduce space
//time-O(n*W) space-O(W)

int main()
{

   
   int n,w;
   cin>>n>>w;
   ll arr[n][2];
   forl(i,0,n)forl(j,0,2)cin>>arr[i][j];

   //O(N*W) space
   ll dp[n+1][w+1];
   
   forl(i,0,w+1) dp[0][i]=0;
   forl(i,0,n+1) dp[i][0]=0;
   forl(i,1,n+1)
   {
       forl(j,0,w+1)
       {
           if(j>=arr[i-1][0])dp[i][j]=max(dp[i-1][j],dp[i-1][j-arr[i-1][0]]+arr[i-1][1]);
           else dp[i][j]=dp[i-1][j];
       }
   }
//    ll maxi=-1;
//    forl(i,0,w+1)maxi=max(maxi,dp[n][i]);
//    cout<<maxi<<endl;
    cout<<dp[n][w]<<endl;



//O(W) space
// if i==0 means i is even else i is odd
    //ll dp[2][w];
    // forl(i,0,w+1)dp[0][i]=0;
    // forl(i,0,2) dp[i][0]=0;
    // forl(i,1,n)
    // {

    // }

}


Measured memory_bytes: 79104
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
    int S;
    cin >> S;
    int x, y ;
    x = S /100;
    y = S % 100;
    if ( 1 <= x && x <= 12){
        if ( 1 <= y && y <= 12)cout << "AMBIGUOUS" << endl;
        else cout << "MMYY" << endl;
    }else{
        if(1 <= y && y <= 12) cout << "YYMM" <<endl;
        else cout << "NA" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        int k=Integer.parseInt(bu.readLine());
        String s=bu.readLine();
        if(k<s.length()) s=s.substring(0,k)+"...";
        System.out.print(s);
    }
}


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

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


Measured memory_bytes: 256