akhauriyash/Code-Regression huggingface dataset:
/*
ID:wmj20041
TASK:
LANG:C++
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9+7;
int n,m;
string s;
bool prime(int n)
{
    if(n==1) return false;
    if(n==2||n==3) return true;
    if(n%6!=1&&n%6!=5) return false;
    for (int i=5;i*i<=n;i+=6)
    if (n%i==0||n%(i+2)==0) return false;
    return true;
}
int check(int x,int y)
{
	if (x>n||x<1||y>=m||y<0) return 0;
	return 1;
}
long long gcd(long long a, long long b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}
inline int read()
{
    int X=0,w=1;
	char c=getchar();
    while (c<'0'||c>'9')
    {
		if (c=='-') w=-1;
		c=getchar();
    }
    while (c>='0'&&c<='9')
	{
	 	X=(X<<3)+(X<<1)+c-'0';
		c=getchar();
	}
    return X*w;
}
int main()
{
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);
	cin>>s;
	int a=0,b=0;
	for (int i=0;i<s.size();i++)
	if (s[i]=='o') a++; else b++;
	if (b>=8) cout<<"NO"; else cout<<"YES";
	return 0;
}

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

int main() {
  string s;
  cin >> s;
  if(s=="Sunny") cout << "Cloudy";
  else if(s=="Cloudy") cout << "Rainy";
  else cout << "Sunny";
  
  cout << endl;
}


Measured memory_bytes: 256
<?php
fscanf(STDIN, '%d', $n);
$h = array_map('intval', explode(' ', trim(fgets(STDIN))));

$max = $h[0];
$ans = 0;
for ($i = 0; $i < $n; $i++) {
    if ($h[$i] >= $max) $ans++;
    $max = max($max, $h[$i]);
}
echo $ans . PHP_EOL;

Measured memory_bytes: 4856
#include<stdio.h>

int gcd(int a, int b){
    return a%b==0 ? b : gcd(b,a%b);
}

int main() {
    int k,a,b,c;
    long int sum=0;
    scanf("%d",&k);

    for(a=1; a<=k; a++)
        for(b=1; b<=k; b++)
            for(c=1; c<=k; c++){
                if(a<=b<=c) {if(gcd(c,b) >= a) sum+=gcd(gcd(c,b),a); 
                                else sum+=gcd(a,gcd(c,b)); }
                else if(a<=c<=b) {if(gcd(b,c)>=a) sum+=gcd(gcd(b,c),a); 
                                    else sum+= gcd(a,gcd(b,c)); }
                if(b<=a<=c) {if(gcd(c,a) >= b) sum+=gcd(gcd(c,a),b); 
                                else sum+=gcd(b,gcd(c,a)); }
                else if(b<=c<=a) {if(gcd(a,c)>=b) sum+=gcd(gcd(a,c),b); 
                                    else sum+= gcd(b,gcd(a,c)); }
                if(c<=b<=a) {if(gcd(a,b) >= c) sum+=gcd(gcd(a,b),c); 
                                else sum+=gcd(c,gcd(a,b)); }
                else {if(gcd(b,a)>=c) sum+=gcd(gcd(b,a),c); 
                                    else sum+= gcd(c,gcd(b,a)); }
            }
    printf("%d",sum/3);
                
    return 0;

}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=(a);i<(n);i++)
#define SZ(a) int((a).size())
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;

int main() {
	string s;
	cin>>s;
	if (s.size()<4||s.substr(0,4)!="YAKI") puts("No");
	else puts("Yes");
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <unordered_map>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define y1 abcde
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f;
const int N = 5e2 + 15;
int n, m, a[N][N], b[N][N], c[N][N];
bool used[N][N];
vector <int> col[N], row[N];

inline bool check(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

void dfs(int x, int y) {
    used[x][y] = true;
    c[x][y] = 1;
    for(int i = 0; i < 4; ++i) {
        int tox = dx[i] + x, toy = dy[i] + y;
        if(check(tox, toy) && !used[tox][toy] && (!b[tox][toy] || a[tox][toy])) {
            dfs(tox, toy);
        }
    }
}

main() {
    scanf("%d %d\n", &n, &m);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            char c = getchar();
            a[i][j] = (c == '#');
            if(a[i][j]) {
                b[i][j] = 1;
                col[j].pb(i), row[i].pb(j);
            }
        }
        getchar();
    }
    for(int i = 2; i < n; i += 2)
        for(int j = 2; j < m; ++j)
            b[i][j] = 1;
    for(int i = 2; i < n; ++i)
        b[i][2] = 1;
    dfs(1, 1);
    for(int i = 1; i <= n; ++i, cout << endl)
        for(int j = 1; j <= m; ++j)
            cout << (b[i][j] ? '#' : '.');
    puts("");
    for(int i = 1; i <= n; ++i, cout << endl)
        for(int j = 1; j <= m; ++j)
            cout << (c[i][j] ? '#' : '.');
    return 0;
}

Measured memory_bytes: 17792
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 100010;
typedef long long ll;

int n,m,k;
int sum;
int mod;
int a[maxn];

void test(const int A[])
{
	for (int i=1;i<=n;i++)
		cout << A[i] << " ";
	cout << endl;
}

void test(const vector<int> V)
{
	for (int i=0;i<V.size();i++)
		cout << V[i] << " ";
	cout << endl;
}

void solve()
{
	scanf("%d %d %d",&n,&m,&sum);
	
	for (int i=0;i<m;i++)
	{
		cout << sum << " ";
	}
	if(sum == 1000000000)
	{
		for (int i=0;i<n-m;i++)
		{
			cout << sum-1 << " ";
		}
		cout << endl;
	} 
	else
	{
		for (int i=0;i<n-m;i++)
		{
			cout << sum+1 << " ";
		}
		cout << endl;
	}
}

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

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

typedef long long ll;

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

    ll x[N];
    for(int i=0; i<N; i++) {
	cin >> x[i];	
    }
    
    ll ans = 0;
    for(int i=0; i<N-1; i++) {
	ans += min(B,(x[i+1]-x[i])*A);
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
    lint n, W;
    cin >> n >> W;

    vector<lint> w(n), v(n);
    for(lint i=0; i<n; i++)  cin >> w[i] >> v[i];

    map<lint, lint> dp;
    dp[0] = 0;
    for(lint i=0; i<n; i++) {
        map<lint, lint> dp_tmp(begin(dp), end(dp));
        for(auto e : dp) {
            lint key, value;
            tie(key, value) = e;
            dp_tmp[key + w[i]] = max(dp_tmp[key + w[i]], dp[key] + v[i]);
        }
        dp = dp_tmp;
    }

    lint ans = 0;
    for(auto e : dp) {
        lint key, value;
        tie(key, value) = e;
        if(key > W)  break;
        ans = max(ans, value);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
(let* ((h (read))
    (w (read))
    (a (make-array (list h w) :initial-element 0))
    (b 0))

    (loop for i below h do
        (let ((s (read-line)))
            (if (null (find #\# s))
                (incf b)
                (loop for j below w do
                    (setf (aref a (- i b) j) (char s j))
                )
            )
        )
    )
    (loop for j below w do
        (let ((flg nil))
            (loop for i below (- h b) do
                (if (string= (aref a i j) "#")
                    (progn
                        (setq flg T)
                        (return)
                    )
                )
            )
            (if (null flg)
                (loop for i below (- h b) do
                    (setf (aref a i j) "0")
                )
            )
        )
    )
    (loop for i below (- h b) do
        (progn
            (loop for j below w do
                (if (not (string= (aref a i j) "0"))
                    (format t "~A" (aref a i j))
                )
            )
            (format t "~%")
        )
    )
)

Measured memory_bytes: 25052
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cctype>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cstring>
#include<list>
#include<sstream>
//#include<windows.h>
//#include<time.h>
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mer make_pair
#define mme memset
#define ao(a) (a.begin(),a.end())
using namespace std;

const double pie1=3.1415926;//π1
const double pie2=3.14159265358979;//π2
const double pie3=3.14159265358979323846;//π3
const int vbi=999999999;
const int vli=-vbi;
const long long vbl=999999999999999999;
const long long vll=-vbl;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> piii;
typedef pair<pii,pii> pi4;
typedef pair<pll,ll> plll;
typedef pair<int,pii> ipii;
typedef pair<ll,pll> lpll;
typedef pair<pll,pll> pl4;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef set<int> sti;
typedef set<ll> stl;
typedef set<pii> spi;
typedef set<pll> spl;
priority_queue<int> pqi;
priority_queue<ll> pql;
queue<int> qi;
queue<ll> ql;

/*void bin_v(){
	char bin[1000];
	gets(bin);
}*/

bool pss(int a){
	for(int i=2;i<=sqrt(a);i++)
		if(a%i==0)
			return false;
	return true;
}
/////////////////////////////////////////////////////////////////////////////////////////

int doit(int size_){
	int ans=size_/3,p=0;
	if(ans*3<size_)
		p++;
	return ans*2+p;
}

int main(){
	//my name is Veex_WCY
	ios::sync_with_stdio(false);
	string str;
	cin>>str;
	int en=str.size()-1;
	for(int i=str.size()-2;i>=0;i--)
		if(str[i]==str[i+1])
			en=i;
		else
			break;
	if(en==0){
		cout<<doit(str.size()-en);
		return 0;
	}
//	cout<<en<<endl;
	string old="";
	int ans=0;
	for(int i=0;i<en;i++){
		ans++;
		stringstream stream;
		stream<<str[i];
		string sss=stream.str();
//		cout<<sss<<'-'<<old<<'-'<<(sss==old)<<endl;
		if(sss!=old){
			old=str[i];
		}
		else{
			int sz=1,j=i;
			do{
				sz++;
				j++;
				if(i+sz-1>=en)
					en++;
			}while(str.substr(i,sz)==old);
			old=str.substr(i,sz);
			i=j;
		}
//		cout<<i<<endl;
	}
//	cout<<en<<endl;
//	cout<<doit(str.size()-en)<<endl;
	cout<<ans+doit(str.size()-en);
	return 0;
}


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

using namespace std;
int arr[11];
int ans = 1e9;
int mx;

bool valid(int x) {
    while (x) {
        if (arr[x % 10]) return 0;
        x /= 10;
    }
    return 1;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int x;
    while (k--) {
        scanf("%d", &x);
        arr[x] = 1;
    }
    for (;; ++n) {
        if (valid(n)) break;
    }
    printf("%d", n);
}

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

int main() {
  string s, str;
  getline(cin, str);
  stringstream ss(str);
  while (getline(ss, s)) {
    for (size_t i = 0; i < str.size(); i++) {
      char ch = str.at(i);
      if ('A' <= ch && ch <= 'Z')
        cout << (char)(ch + 32);
      else if ('a' <= ch && ch <= 'z')
        cout << (char)(ch - 32);
      else
        cout << ch;
    }
    cout << endl;
  }
}


Measured memory_bytes: 3148
#include <cstdio>
#include <string>
#include <list>
#include <algorithm>

int getValue(std::string text) {
    char number[11];
    std::snprintf(number, text.length(), "%s\n", text.c_str());
    return std::atoi(number);
}

int main() {

    const int BUF_SIZE = 24;

    int commandCount;
    std::scanf("%d\n", &commandCount);

    std::list<int> list;
    while (commandCount--) {
        char command[BUF_SIZE];
        std::fgets(command, sizeof(command), stdin);
        std::string command_str(command);

        if (command_str.substr(0, 6) == "insert") {
            auto number = command_str.substr(7);
            int value = getValue(number);
            list.emplace_front(value);
        } else if (command_str.substr(0, 11) == "deleteFirst") {
            list.pop_front();
        } else if (command_str.substr(0, 10) == "deleteLast") {
            list.pop_back();
        } else if (command_str.substr(0, 6) == "delete") {
            auto number = command_str.substr(7);
            int value = getValue(number);
            const auto deleteItr = std::find(list.begin(), list.end(), value);
            if (deleteItr != list.end()) {
                list.erase(deleteItr);
            }
        }
    }

    auto itr = list.cbegin();
    const auto endItr = list.cend();
    std::printf("%d", *itr);
    for (++itr; itr != endItr; ++itr) {
        std::printf(" %d", *itr);
    }
    std::puts("");

    return 0;

}

Measured memory_bytes: 34148
from collections import Counter
n = int(input())
s = input()
slen = len(s)
d = Counter(s)
res = d['R']*d['G']*d['B']
#print(res)
for start in range(slen):
    for step in range(1, slen):
        i = start
        j = i + step
        k = j + step
        if k >= slen:
            break
        ijk = [s[i], s[j], s[k]]
        # print("ijk is", ijk)
        if 'R' in ijk and 'G' in ijk and 'B' in ijk:
            res -= 1

print(res)


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

#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n;
  cin >> n;
  cout << n*n*n << endl;
  return 0;
}



Measured memory_bytes: 3088
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import pdb
import sys
F = sys.stdin
K, S = map(int,F.readline().split())
count = 0
for x in range(K+1):
    yplusz = S - x
    for y in range(yplusz+1):
        z = yplusz - y
        if z <= K and y <= K:
            count += 1

print(count)


Measured memory_bytes: 52716
import math
from itertools import combinations, permutations

def dist(x1, y1, x2, y2):
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** .5


n = int(input())
xy = [[int(i) for i in input().split()] for _ in range(n)]
edges = list(range(n))
memo = {}
res = 0
for p in permutations(edges):
    for i, a in enumerate(p[1:], start=1):
        b = p[i - 1]
        if (a, b) in memo:
            res += memo[a, b]
        else:
            d = dist(xy[a][0], xy[a][1], xy[b][0], xy[b][1])
            memo[a, b] = d
            memo[b, a] = d
            res += d
print(res / math.factorial(n))

Measured memory_bytes: 41324
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,c,a,b=0,d;
    cin >> n >> c;
    for (int i=0; i < c;i++){
        cin >> a;
        b = b + a;
    }
    if(b%(n+1)>0){
        cout << b/(n+1)+1 << endl;
    }else{
        cout << b/(n+1) << endl;
    }

}


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

using namespace std;

typedef long long int ll;

ll go(pair<ll,ll> p1 , pair<ll,ll> p2)
{
    ll dis = 0;
    dis = abs(p1.first - p2.first) + abs(p1.second - p2.second);
    return dis;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    vector<pair<ll,pair<ll,ll>> > v,v2,v3,v4;
    for(int i=0 ; i<n ; i++)
    {
        ll x,y;
        cin >> x >> y;
        v.push_back({x+y,{x,y}});
        v2.push_back({x-y,{x,y}});

    }
    sort(v.begin(),v.end());
    sort(v2.begin(),v2.end());
    ll a1=0,a2=0;

    pair<ll,ll> p1,p2,p3,p4;

    p1 = v[0].second;
    p2 = v[n-1].second;

    p3 = v2[0].second;
    p4 = v2[n-1].second;

    cout << max(go(p1,p2),go(p3,p4));

    return 0;
}


Measured memory_bytes: 12760
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define INF 1e9

using vi=vector<int>;
using vvi=vector<vi>;

vvi matmul(vvi a, vvi b){
	int n=a.size();
	auto d=vvi(n,vi(n,0));
	rep(i,n)rep(j,n)rep(k,n) d[i][j]|=a[i][k]*b[k][j];
	return d;
}

vvi matpow(vvi a,int p){
	static map<int,vvi> memo;
	memo[1]=a;
	if(memo.find(p)==memo.end()){
		memo[p]= p%2 ? matmul(matpow(a,p-1),a) : matmul(matpow(a,p/2),matpow(a,p/2));
	}
	return memo[p];
}

int main(){
	int n,m,a[3];
	while(cin>>n>>m>>a[0]>>a[1]>>a[2]){
		vvi z(n,vi(n,0));
		auto e=z;
		rep(_,m){
			int p,q; cin>>p>>q;
			e[p-1][q-1]=1;
		}

		vector<vvi> d(3);
		auto f=e;
		rep(p,3){
			d[p]=matpow(e,a[p]);
		}
		
		vi g(n,0);
		g[n-1]=1;
		rep(t,1000){
			bool next=0;
			vi ng(n,0);
			rep(i,n) if(!g[i]){
				bool ok=1,r;
				rep(p,3) [&]{r=0; rep(j,n) r|=(g[j] and d[p][i][j]); ok&=r;}();
				if(ok) ng[i]=next=1;
			}
			if(!next){
				cout<<"IMPOSSIBLE"<<endl;
				break;
			} else if(ng[0]){
				cout<<t+1<<endl;
				break;
			}
			rep(i,n)g[i]|=ng[i];
		}
	}
	return 0;
}



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

namespace _20190308_05 {
    class Program {
        static void Main(string[] args) {
            var line = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            if (line[1] % line[0] == 0) {
                Console.WriteLine(line.Sum());
            } else {
                Console.WriteLine(line[1] - line[0]);
            }
        }
    }
}


Measured memory_bytes: 13396
/// Containers Start
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// C Header Files
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <math.h>
#include <stdio.h>
/// Containers End

using namespace std;

/// Math Start
#define PI acos(-1.0)
#define Pi 3.141592653589793
#define EPS (1e-7)
#define INF (0x3f3f3f3f)
/// Math End

/// Extra Start
#define nn '\n'
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define sz(a) int((a).size())
#define space " "
#define All(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
/// Extra End

#define rep(i, n) for (int i = 0; i < n; i++)
#define Cini(a)                                                                \
    int a;                                                                     \
    cin >> a;
#define Cinii(a, b)                                                            \
    int a, b;                                                                  \
    cin >> a >> b;
#define Ciniii(a, b, c)                                                        \
    int a, b, c;                                                               \
    cin >> a >> b >> c;
#define Cins(s)                                                                \
    string s;                                                                  \
    cin >> s;
#define Cinss(s1, s2)                                                          \
    string s1, s2;                                                             \
    cin >> s1 >> s2;
#define Cinc(c)                                                                \
    char c;                                                                    \
    cin >> c;
/// Functions End


/// Debug Start
#define deb(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << '\t' << #y << ": " << y << endl;
#define deb3(x, y, z)                                                          \
    cout << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": "   \
         << z << endl;
/// Debug End

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

/**>>>>>>>>>>>>>>>>>>> END <<<<<<<<<<<<<<<<<<**/

/// template


signed main(void) {
    cin.sync_with_stdio(false);
    cin.tie(0);
    Cins(s);
    int count = 0;
    rep(i, s.length()) { if (s[i] == 'o') count++; }
    if(count + 15 - s.length() >=8) cout << "YES" << nn;
    else cout << "NO" << nn;
    return 0;
}

Measured memory_bytes: 256
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
bool check(int X,int Y,int x1,int y1,int h1,int x2,int y2,int h2){
  if(abs(X-x1) + abs(Y-y1) - abs(X-x2) - abs(Y -y2) == h2 - h1){
    return true;
  }
  return false;
}
std::vector<std::vector<int>> updateMap(std::vector<std::vector<int>> map,int x1,int y1,int h1,int x2,int y2,int h2){
  if(h1 == 0 || h2 == 0){
    if(h1 == 0){
      map[x1][y1] = 1;
    }else{
      map[x2][y2] = 1;
    }
  }else{
    for(int i = 0; i < 101; i++){
      for(int j = 0; j < 101; j++){
        if(check(i,j,x1,y1,h1,x2,y2,h2)){
          
        }else{
          map[i][j] = 1;
        }
      }
    }
  }

  return map;
}
bool checkOnlyOne (std::vector<std::vector<int>> map){
  int tmp = 0;
  for(int i = 0; i < 101; i++){
    for(int j = 0; j < 101; j++){
      if(map[i][j] == 0){
        tmp++;
      }
    }
  }
  return tmp == 1;
}
int main()
{
  std::vector<std::vector<int>> m;
  m.resize(101);		// ()内の数字が要素数になる
  for( int i=0; i<101; i++ ){
    m[i].resize(101);
  }
  int N;
  cin >> N;
  int x1,y1,h1,x2,y2,h2;
  int X[N],Y[N],H[N];
  int cx,cy,ch;
  std::vector<int> candx;
  std::vector<int> candy;
  std::vector<int> candh;
  cin >> x1 >> y1 >> h1;
  X[0] = x1;
  Y[0] = y1;
  H[0] = h1;
  for(int i = 1; i < N; i++){
    cin >> x2 >> y2 >> h2;
    X[i] = x2;
    Y[i] = y2;
    H[i] = h2;
      m = updateMap(m,x1,y1,h1,x2,y2,h2);
      if(checkOnlyOne(m)){
        break;
      }
      x1 = x2;
      y1 = y2;
      h1 = h2;

  }
  if(!checkOnlyOne(m)){
    int tmp = 0;
    for(int i = 0; i < N; i++){
      if(H[tmp] < H[i]){
        tmp = i;
      }
      
    }
    cout << X[tmp] << " " << Y[tmp] << " " << H[tmp] << endl;
  }else{
    for(int i = 0; i < 101; i++){
      for(int j = 0; j < 101; j++){
        if(m[i][j] == 0){
          cout << i << " " << j << " " << h1 + abs(i - x1) + abs(j - y1) << endl;
          break;
        }
      }
    }
  }
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
#include <set>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=200010;
int fa[N];
bool vis[N];
int nodes[N],ns=0;
int mex1[N],mex2[N];
namespace T{
	const int E=N;
	int to[E],bro[E],head[N],e=0;
	inline void init(){
		memset(head,-1,sizeof(head));
	}
	inline void ae(int u,int v){
		to[e]=v,bro[e]=head[u],head[u]=e++;
	}
	void dfs(int x){
		set<int>s;
		for(int i=head[x],v;~i;i=bro[i]){
			dfs(v=to[i]);
			s.insert(mex1[v]);
		}
		for(int &i=mex1[x]=0;s.find(i)!=s.end();i++);
		for(int &i=mex2[x]=mex1[x]+1;s.find(i)!=s.end();i++);
	}
}
inline int gval(int sg){
	for(int i=1;i<=ns;i++){
		sg=(sg!=mex1[nodes[i]]?mex1:mex2)[nodes[i]];
	}
	return sg;
}
inline bool Main(){
	int n=ni;
	T::init();
	for(int i=1;i<=n;i++){
		fa[i]=ni;
	}
	memset(vis,0,sizeof(vis));
	int x=1;
	for(;!vis[x];vis[x]=true,x=fa[x]);
	memset(vis,0,sizeof(vis));
	for(int p=x;nodes[++ns]=p,vis[p]=true,p=fa[p],p!=x;);
	T::init();
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			T::ae(fa[i],i);
		}
	}
	for(int i=1;i<=ns;i++){
		T::dfs(nodes[i]);
	}
	int val1=mex1[nodes[ns]],val2=mex2[nodes[ns]];
	return gval(val1)==val1||gval(val2)==val2;
}
int main(){
	puts(Main()?"POSSIBLE":"IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 5248
#include <stdio.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
using namespace std;

// Self settings
// clang-format off
#define MAX_N 10000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
// clang-format on

typedef long long ll;

int N;
ll x[MAX_N], y[MAX_N];
ll p, q;
typedef pair<ll, ll> P;

map<P, ll> a;
map<double, ll> b;
priority_queue<P> que;

void solve()
{
  set<P> st;
  for (int i = 0; i < N; i++) {
    st.insert(P(x[i], y[i]));
  }

  int ret = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (i == j) continue;
      P p = P(x[i] - x[j], y[i] - y[j]);
      int cnt = 0;
      for (int k = 0; k < N; k++) {
        P q = P(p.first + x[k], p.second + y[k]);
        if (st.count(q)) cnt++;
      }
      ret = max(ret, cnt);
    }
  }
  cout << N - ret << endl;
}

int main(void)
{
  cin >> N;
  REP(i, N) cin >> x[i] >> y[i];
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <assert.h>
#include <numeric>
#include <climits>

using namespace std;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
int m[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
bool cmp(int a, int b) {
    return m[a] < m[b];
}

int dp[10001];
int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> As;
    REP(i, M) {
        int A;
        cin >> A;
        As.push_back(A);
    }
    
    
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        dp[i] = -INT_MAX;
        REP(j, 9) {
            if (find(all(As), j+1) != As.end() && i-m[j+1]>=0) dp[i] = max(dp[i - m[j+1]]+1, dp[i]);
        }
    }
    
    sort(all(As));
    
    int n = N;
    while(n>0) {
        REP(i, M) {
            int A = As[M-1-i];
            if (n-m[A] >= 0 && dp[n-m[A]] == dp[n]-1) {
                n -= m[A];
                cout << A;
                break;
            }
        }
        
    }
    
    cout << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace lineAralgebra
{
	class Program
	{
		static void Main(string[] args)
		{
			var n = int.Parse(Console.ReadLine());

			var list = new List<int>();

			for (int i = 0; i < n; i++)
			{
				list.Add(int.Parse(Console.ReadLine()));
			}

			var tempArray = new List<int>(list);

			tempArray.Sort();
			var max = tempArray.Last();
			// Console.WriteLine("");

			for (var i = 0; i < n; i++)
			{
				if (list[i] != max) 
				{
					Console.WriteLine(max);
				} else 
				{
					Console.WriteLine(tempArray[tempArray.Count -2]);
				}
			}
		}
	}
}

// 3
// 1
// 4
// 3

Measured memory_bytes: 19156
import java.util.Scanner;
public class Main
{
  public static void main(String[] args)
  {
    Scanner sc=new Scanner(System.in);
    String a=sc.next();
    String b=sc.next();
    String c=a+b;
    int k=Integer.parseInt(c);
    int count=0;
    for(int i=1;i<=Math.sqrt(k);i++)
    {
      if(i*i==k)
      {
        System.out.println("Yes");
        count=1;
        break;
      }
      else count++;
    }
    if(count>1) System.out.println("No");
  } 
}

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

const int N = 305;
const int MOD = 998244353;

int n, m, f[N][N][N], s[N], a[N];
char str[N];

int main()
{
	scanf("%s%d", str + 1, &m);
	n = strlen(str + 1);
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + (str[i] == '1');
	int tot = 0, ls = 0;
	for (int i = 1; i <= n; i++)
		if (str[i] == '0') a[++tot] = s[i] - s[ls], ls = i;
	a[++tot] = s[n] - s[ls];
	for (int i = 1; i <= tot; i++) s[i] = s[i - 1] + a[i];
	f[0][0][0] = 1;
	for (int i = 0; i < tot; i++)
		for (int j = s[i]; j <= s[tot]; j++)
			for (int k = 0; k <= j; k++) if (f[i][j][k])
				for (int l = max(0, s[i + 1] - j); l <= s[tot] - j; l++)
					if (l > a[i + 1]) (f[i + 1][j + l][k + l - a[i + 1]] += f[i][j][k]) %= MOD;
					else (f[i + 1][j + l][k] += f[i][j][k]) %= MOD;
	int ans = 0;
	for (int i = 0; i <= min(n, m); i++) (ans += f[tot][s[tot]][i]) %= MOD;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 30592
#include<bits/stdc++.h>
    #define ll long long
    #define rep(i,a,b) for(i=a;i<b;i++)
    #define pb push_back
    #define all(v) v.begin(),v.end()
    #define F first
    #define S second
    #define CLR(a) memset((a),0,sizeof(a))
    #define mp make_pair
    #define hell 1000000007

    using namespace std;
     //int g[105][105];
    //vector < int > wt(100004);
   // vector < int > a;
    //vector < int > v(30500);
    //int cst[102][100005];
    //int ansr[100005];
 //ll int sum,x=0,c=0,n,m,flag=0,a1,a2,flag1=0,flag2=0;
    //vector < vector < int > > adj(5000, vector < int > (5000));
 //int  dp[1000006];
   // int level[500];




    void solve()
    {
        int i,j=0,r=200,p,q,k=0,ans=0,d,h,flag=0,n,m=0,a,b,id,c,h1,h2,a1,b1;
         cin>>n>>k;
         vector < int > v(n),dp(n,hell);
         rep(i,0,n)
         {
             cin>>v[i];
         }
         dp[0]=0; dp[1]=abs(v[1]-v[0]);
         rep(i,2,n)
            {
                 rep(j,1,k+1){ if(i-j>=0)
                dp[i]=min(dp[i],dp[i-j]+abs(v[i-j]-v[i]));
                 }
            }
            cout<<dp[n-1];



    }



    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int t=1;
        //cin>>t;
        while(t--)
        solve();
    }

       /*

  void bfs( int i , int j)
       {
           vis[i][j]= true;
         queue < int > que;
         que.push(k);
         while(!que.empty())
         {
            int x= que.front();
            que.pop();
             for ( int i=1;i<=n;i++)
             {
                 if((!g[1][n] and g[x][i] ) or (g[1][n] and ! g[x][i]))
                 {
                   if(!vis[i])
                   {
                       que.push(i);
                       level[i]=level[x]+1;
                       vis[i]= true;
                   }
                 }
             }
         }
       }

      ll int por(ll int a,ll int b)
         {
            ll int k=1;
            while(b>0)
            {
                if(b%2) k=k*a,k%=hell;
                b/=2;
                a*=a; a%=hell;
            }
            return k;
         } */


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

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    rep(i, n) cin >> d[i];
    ll tot = 0;
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
            tot += d[i]*d[j];
        }
    }
    cout << tot << endl;
    return 0;
}

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

int main() {
  int H,W;
  cin >> H >> W;
  vector<vector<char>> vec(H,vector<char>(W));
  vector<bool> a(H,false);
  vector<bool> b(W,false);
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
  	cin >> vec.at(i).at(j);
    if(vec.at(i).at(j)=='#'){
      a[i] = true;
      b[j] = true;
    }
    }
  }
  for(int i=0;i<H;i++){
      if(a[i]){
        for(int j=0;j<W;j++){
        if(b[j])
        cout << vec.at(i).at(j);
        }
        cout << endl;
      }
    }
}

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

int main(){
  int N, K;
  string str;
  cin >> N >> K >> str;
  
  //K回の時間に00...0がK箇所入ってよい
  vector<int> v;
  int flag = 1,count = 1;
  if(str[0]=='0')v.push_back(0);
  else if(str.size() <= 1)v.push_back(1);
  for(int i = 1; i < N; i++){
    if(str[i] != str [i - 1]){
      v.push_back(count);
      //flag = flag * -1;
      count = 1;
      if(i == N -1)v.push_back(count);
    }else{
      count++;
      if(i == N -1)v.push_back(count);
    }
  }
  if(str[str.size() - 1] =='0')v.push_back(0);//1......1の形に整形
  /*
  for(int i = 0; i < v.size(); i++){
    cout << v[i] << " ";
  }
  */
  int ans = 0,max = 0;
  //小さいとき
  if(v.size() <= K*2)max = accumulate(v.begin(), v.end(), 0);
  for(int i = 0;i < v.size() - K*2;i += 2){
    if(i + K*2 >= v.size()){
      max = accumulate(v.begin() + i, v.end(), 0);
      if(max > ans)ans = max;
      break;
    }
    max = accumulate(v.begin() + i, v.begin() + i + K*2 + 1, 0);
    if(max > ans)ans = max;
    //cout << "max:" <<max << endl;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 1020
n, k, c = map(int, input().split())
s = list(input())
# print(s)

dp1 = [0] * (n + 1)
for i in reversed(range(n)):
    j = min(i + c + 1, n)
    if s[i] == 'o':
        dp1[i] = max(dp1[j] + 1, dp1[i + 1])
    else:
        dp1[i] = max(dp1[j], dp1[i + 1])

dp2 = [0] * (n + 1)
for i in range(n):
    j = max(i - c - 1, -1)
    if s[i] == 'o':
        dp2[i] = max(dp2[j] + 1, dp2[i - 1])
    else:
        dp2[i] = max(dp2[j], dp2[i - 1])

# print(dp1)
# print(dp2)


def check(idx):
    if s[idx] == 'x':
        return False

    if dp1[idx + 1] + dp2[idx - 1] >= k:
        return False
    else:
        return True


for i in range(n):
    if check(i):
        print(i + 1)


Measured memory_bytes: 63344
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iomanip>

using namespace std;

#define pi 3.141592653589
#define repeat(i,n) for(int i=0;i<n;i++)

int main()
{
	int n;
	int tp = 0, hp = 0;
	string taro, hanako;
	cin >> n;
	repeat(i, n)
	{
		cin >> taro;
		cin >> hanako;
		if (taro > hanako)
		{
			tp = tp + 3;
		}
		else if (taro < hanako)
		{
			hp = hp + 3;
		}
		else if (taro == hanako)
		{
			tp++;
			hp++;
		}
	}
	cout << tp << " " << hp << endl;
	return 0;
}

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

int main(){
  int N,M;
  vector<vector<int>> s;
  vector<int> p;

  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int K;
    cin >> K;
    vector<int> s1;
    for (int j = 0; j < K; j++) {
      int a;
      cin >> a;
      s1.push_back(a);
    }
    s.push_back(s1);
  }

  for (int i = 0; i < M; i++) {
    int b;
    cin >> b;
    p.push_back(b);
  }

  int ans = 0;
  for (int bit = 0; bit < ( 1 << N ); bit++) {
    bitset<10> bs(bit);

    int s_pos = 0;
    int m_on  = 0;
    for (auto s1: s) {
      int sum = 0;
      for (int pos: s1) {
        sum += bs[pos - 1];
      }
      if (sum % 2 == p[s_pos]) m_on++;

      s_pos++;
    }

    if (m_on == M) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ms memset
#define MOD 1000000007
#define sp fixed<<setprecision
#define sz sizeof
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod2=998244353;
ll fpow(ll x,ll y,ll p=MOD){x=x%p;ll sum=1;while(y){if(y&1)sum=sum*x;sum%=p;y=y>>1;x=x*x;x%=p;}return sum;}
ll inv(ll a,ll m=MOD){ll c=m;ll y=0,x=1;if(m==1)return 0;while(a>1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=c;return x;}
ll spf[10005];
void sieve()
{
  for(int i=1;i<10005;i++)
  spf[i]=i;
  for(int i=2;i*i<=10005;i++)
  if(spf[i]==i)
  for(int j=2*i;j<10005;j+=i)
  spf[j]=min(spf[j],(ll)(i));
}

int main(){
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   ll n,d;
   cin>>n>>d;
   ll res=0;
   ll mes=d*d;
   for(int i=0;i<n;i++){
     ll x,y;
     cin>>x>>y;
     ll tmp = x*x + y*y;
     if(tmp<=mes)
      res++;
   }
   cout<<res;

}


Measured memory_bytes: 3640
N,M=map(int,input().split())
L=[]
for i in range(N):
    L.append([int(i)-1 for i in input().split()][1:])
K=[len(L[i]) for i in range(N)]
X=[-1 for i in range(M)]
for i in range(N):
    for j in range(K[i]):
        if X[L[i][j]]==-1:
            X[L[i][j]]=i
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
for i in range(N):
    for j in range(K[i]):
        unite(i,X[L[i][j]])
for i in range(1,N):
    if not(same(0,i)):
        print("NO")
        exit()
print("YES")


Measured memory_bytes: 22804
#include<cstdio>
#define N 500005
#define p 998244353
#define ll long long
inline int mod(int x){return x<p?x:x-p;}
int a[N],b[N],i,m,n,x;
inline int C(int s,int t){return t<=s?(ll)b[t]*b[s-t]%p*a[s]%p:0;}
int main()
{
    scanf("%d%d",&n,&m),*a=*b=a[1]=b[1]=1;
    for(i=2;i<=m;i++)a[i]=(ll)a[i-1]*i%p,b[i]=(ll)(p-p/i)*b[p%i]%p;
    for(i=2;i<=m;i++)b[i]=(ll)b[i]*b[i-1]%p;
    if((~m&1)&&n<=m>>1)x=mod(p+C(m-1,m>>1)-C(m-1,m-n+1));
    for(i=m+2>>1;i<=m;i++)if(n<=i)x=mod(x+mod(p+C(m,i)-C(m,i+i-n+1)));
    return 0&printf("%d\n",x);
}

Measured memory_bytes: 4096
#include <algorithm>
#include <bits/stdc++.h>
#include <deque>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define ll long long
#define REP(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) REP(i, 0, n)
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<ll> vl;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
template <class T> inline void chmax(T &a, T b) { a < b ? a = b : a; };
template <class T> inline void chmin(T &a, T b) { a > b ? a = b : a; };

int main() {
    deque<int> que;
    int q;
    cin >> q;
    rep(i, q) {
        int query;
        cin >> query;
        if(query == 0) {
            int d, x;
            cin >> d >> x;
            if(d == 0) {
                que.push_front(x);
            } else {
                que.push_back(x);
            }
        } else if(query == 1) {
            int p;
            cin >> p;
            cout << que[p] << endl;
        } else {
            int d;
            cin >> d;
            if(d == 0) {
                que.pop_front();
            } else {
                que.pop_back();
            }
        }
    }
}



Measured memory_bytes: 4596
import math
from functools import reduce

def gcd_list(num_list):
    return reduce(math.gcd, num_list)

K = int(input())

sum = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            sum += gcd_list([a, b, c])

print(sum)

Measured memory_bytes: 74728
// う　し　た　ぷ　に　き　あ　く　ん　笑

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

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

    string s;
    cin >> s;
    const int n = s.size();

    vector<int> ans(n, 0);

    // dp[false] 偶数回の移動後に場所iにいる子の数
    // dp[true] 奇数回の移動後に場所iにいる子の数
    array<int, 2> dp = {0, 0};

    // Rマスの子が最終的にどこに行くのか調べる
    // 上のDP表を更新していく
    // i+1マスが'L'ならば、偶数回の移動後に場所iにいる子は最終的に場所iにいる。
    // 奇数回の移動後に場所iにいる子は最終的に場所i+1にいる。

    dp = {};
    for (int i = 0; i < n; i++) {
        reverse(dp.begin(), dp.end());

        if (s[i] == 'R') dp[0]++;
        if (s[i + 1] == 'L') {
            ans[i] += dp[0];
            ans[i + 1] += dp[1];
            dp = {};
        }
    }

    // Lマスの子が最終的にどこに行くのか調べる
    // 走査する方向が後ろから前へだが、上と同じ処理をする
    dp = {};
    for (int i = n - 1; i >= 0; i--) {
        reverse(dp.begin(), dp.end());

        if (s[i] == 'L') dp[0]++;
        if (s[i - 1] == 'R') {
            ans[i] += dp[0];
            ans[i - 1] += dp[1];
            dp = {};
        }
    }

    for (auto i = ans.begin(); i != ans.end(); i++) {
        cout << *i;
        cout << (next(i) != ans.end() ? " " : "\n");
    }
}


Measured memory_bytes: 4200
#include<cstdio>

long long N, X;
long long x[200010];

long long Solve(int groups){
	long long answer = 0;
	for (int i = 0; i < groups; ++i){
		answer += x[N - 1 - i];
		for (long long j = 0; N - 1 - i - groups*j >= 0; j++) answer += (j + 2)*(j + 2)*(N - 1 - i - groups*(j + 1) >= 0 ? x[N - 1 - i - groups*j] - x[N - 1 - i - groups*(j + 1)] : (x[N - 1 - i - groups*j]));
	}
	return answer;
}

int main(){
	scanf("%lld %lld", &N, &X);
	for (int i = 0; i < N; ++i) scanf("%lld", &x[i]);
	int ub = N, lb = 1;
	while(ub > lb){
		int mid = ub + lb + 1 >> 1;
		if(Solve(mid) <= Solve(mid + 1) + X) ub = mid - 1;
		else lb = mid;
	}
	long long min = Solve(lb) + X*(lb + N);
	if(lb < N && Solve(lb + 1) + X*(lb + 1 + N) < min)min = Solve(lb + 1) + X*(lb + 1 + N);
	if(lb > 1 && Solve(lb - 1) + X*(lb - 1 + N) < min)min = Solve(lb - 1) + X*(lb - 1 + N);
	printf("%lld\n", min);
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
typedef pair<ii,int> iii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define eb emplace_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"LINE %d: (%s) = ",__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }

const ll MAXn=5e3+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll dp[MAXn][MAXn];
ii d[MAXn];
int main(){
    IOS();
    int n;
    cin >> n;
    REP1 (i,n) {
        cin >> d[i].X >> d[i].Y;
    }
    sort(d+1,d+n+1,[&](const ii a,const ii b){
        return a.X + a.Y < b.X + b.Y;
    });
    REP (i,n+1) REP (j,n+1) dp[i][j] = INF;

    dp[0][0] = 0;
    REP1 (i,n) {
        for (ll j=0;j<=i;j++) {
            if (!j) dp[i][j] = 0;
            else {
                dp[i][j] = dp[i-1][j];
                if (dp[i-1][j-1] <= d[i].X) {
                    dp[i][j] = min(dp[i][j],dp[i-1][j-1] + d[i].Y);
                }
            }
        }
    }
    ll ans = 0;
    REP1 (i,n) {
        if (dp[n][i] != INF) ans = i;
    }
    cout << ans << endl;
}


Measured memory_bytes: 195968
#include <iostream>
using namespace std;
typedef long long ll;
ll a,b;
ll f(ll n){
    ll m=n%4;
    if(m==0)return n;
    if(m==1)return 1;
    if(m==2)return n^1;
    else return 0;
}
int main(void){
    cin>>a>>b;
    a=max(a-1,0LL);
    cout<<(f(a)^f(b))<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
    
    int a, b;
    char op;
    int x;

    while(true)
    {
    scanf("%d %c %d", &a, &op, &b);

    if(op=='?') break;

        switch(op){
        case '+' : 
            x = a+b;
            printf("%d\n", x);
            break;
        case '-' :
            x = a-b;
            printf("%d\n", x);
            break;
        case '*' :
            x = a*b;
            printf("%d\n", x);
            break;
        case '/' :
            if(b==0) break;
            x = a/b;
            printf("%d\n", x);
            break;
        }
    }

return 0;
}



Measured memory_bytes: 2764
fun main() {
    val (n, k) = readInts()
    val a = readInts()

    var rm = 0
    var curr = k
    while (curr < n) {
        if (a[curr] > a[rm]) println("Yes")
        else println("No")
        rm++
        curr++
    }
}

// Input Reader
private fun readLn() = readLine()!!

private fun readStrings() = readLn().trim().split(" ")
private fun readInts() = readStrings().map { it.toInt() }


Measured memory_bytes: 69300
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using static ConsoleApp.Util;
using static System.Math;

namespace ConsoleApp
{
    class Program
    {

        static void Main(string[] args)
        {
            int n = int.Parse(ReadLine());
            var dic = new Dictionary<string,int>();
            int max = 0;
            for (int i = 0; i < n;i++)
            {
                var s = ReadLine();
                if(dic.ContainsKey(s))
                {
                    dic[s]++;
                }
                else
                {
                    dic[s] = 1;
                }
                if(max < dic[s])
                    max = dic[s];
            }
            var ans = dic.Where(x => x.Value == max)
            .Select(x=>x.Key)
            .OrderBy(x=>x,StringComparer.OrdinalIgnoreCase)
            .ToList();
            
            WriteLine(string.Join("\n",ans));
        }

    }


    static class Util
    {
        public static void ChMin(ref long a, long b)
        {

            if (a > b)
            {
                a = b;
            }
        }

        public static void ChMax(ref long a, long b)
        {
            if (a < b)
            {
                a = b;
            }
        }




    }
}


Measured memory_bytes: 51704
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
A = inpl()

def lcm(A):
    from fractions import gcd
    x = A[0]
    for a in A:
        x = (x * a) // math.gcd(x, a)
    return x

l = lcm(A)

ans = 0
for a in A:
    ans += l // a

print(ans % mod)

    

Measured memory_bytes: 31900
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int h, w, k;
  cin >> h >> w >> k;
  vector<string> s(h);
  for (auto&& e : s) {
    cin >> e;
  }
  int res = 1e9;
  for (int bt = 0; bt < 1 << (h - 1); ++bt) {
    vector<int> p{0};
    for (int i = 1; i < h; ++i) {
      if (bt >> (i - 1) & 1) {
        p.push_back(i);
      }
    }
    p.push_back(h);
    int n = p.size() - 1;
    int cur = n - 1;
    int l = 0, r = 0;
    while (l < w) {
      vector<int> c(n);
      while (r < w) {
        for (int t = 0; t < n; ++t) {
          for (int i = p[t]; i < p[t + 1]; ++i) {
            c[t] += s[i][r] == '1';
          }
        }
        if (*max_element(begin(c), end(c)) > k) {
          break;
        }
        ++r;
      }
      if (l == r) {
        cur = 1e9;
        break;
      }
      l = r;
      cur += l < w;
    }
    res = min(res, cur);
  }
  cout << res << '\n';
}

Measured memory_bytes: 256