akhauriyash/Code-Regression huggingface dataset:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    void run() {
        Scanner sc = new Scanner(System.in);
        char[] arr = sc.next().toCharArray();
        int n = arr.length;

        long sum = 0;

        int current = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == '<') {
                current++;
                max = Math.max(max, current);
            } else {
                current = 0;
            }
            sum += current;
        }
//        debug(sum, max, current);

        current = 0;
        int min = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == '>') {
                current--;
                min = Math.min(min, current);
            } else {
                current = 0;
            }
            sum += Math.abs(current);
        }
//        debug(sum, min, current);

        List<Integer> list = new ArrayList<>();
        int c = 1;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] == arr[i + 1]) c++;
            else {
                list.add(c);
                c = 1;
            }
        }
        list.add(c);
        int n2 = list.size();

//        debug(list);

        if (arr[0] == '<') {
            for (int i = 0; i < n2 - 1; i = i + 2) {
                int x = Math.min(list.get(i), list.get(i + 1));
//            debug(sum, x);
                sum -= x;
            }
        } else {
            for (int i = 1; i < n2 - 1; i = i + 2) {
                int x = Math.min(list.get(i), list.get(i + 1));
//            debug(sum, x);
                sum -= x;
            }
        }


        System.out.println(sum);

    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

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


Measured memory_bytes: 33664
#include <iostream>
#include <vector>
 
const int MAX_N = 100001;
int N;
std::vector<std::pair<int,int> > ds[MAX_N];
int ans[MAX_N];
 
void dfs(int x, int y){
   
   for(int i=0; i<ds[x].size(); ++i){
      int n = ds[x][i].first;
      if(n==y) continue;
      if(ds[x][i].second%2) ans[n] = ans[x] ? 0 : 1;
      else ans[n] = ans[x];
      dfs(n,x);
   }
   return;
}
 
int main(){
   std::cin >> N;
   int u, v, w;
   for(int i=0; i<N-1; ++i){
      std::cin >> u >> v >> w;
      ds[u].push_back(std::make_pair(v,w));
      ds[v].push_back(std::make_pair(u,w));
   }
 
   dfs(1,1);
   for(int i=1; i<=N; ++i){
      std::cout << ans[i] << std::endl;
   }
 
   return 0;
 
}


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

int main(){
	int n,d,x;
	cin >> n >> d >> x;
	vector<vector<int> > p(d, vector<int>(n));
	for(int i=0; i<d; i++){
		for(int j=0; j<n; j++){
			cin >> p[i][j];
		}
	}
	
	for(int i=0; i<d-1; i++){
		vector<vector<int> > dp(n+1, vector<int>(x+1, 0));
		for(int j=0; j<n; j++){
			for(int k=0; k<=x; k++){
				if(k - p[i][j] >= 0){
					dp[j+1][k] = max(dp[j][k], dp[j+1][k-p[i][j]] + p[i+1][j]-p[i][j]);
				}else{
					dp[j+1][k] = dp[j][k];
				}
			}
		}
		x += dp[n][x];
	}
	cout << x << endl;
	return 0;
}

Measured memory_bytes: 4184
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
  vector <long long int> v,w;
  int n;
  
  scanf("%d", &n);
  for (int i=0; i<n; i++){
    long long tmp;
    scanf("%lld", &tmp);
    v.push_back(tmp);
    w.push_back(tmp);
  }
  sort(v.begin(), v.end());
//  for (int i=0; i<n; i++){
//    printf("%lld ", v[i]);
//  }puts("");
  for (int i=0; i<n; i++){
    if (w[i]>=v[n/2]){
      printf("%lld\n", v[n/2-1]);
    }else{
      printf("%lld\n", v[n/2]);
    }
}
  return 0;
}

Measured memory_bytes: 5476
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T> inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();
    
    int n, m, q;
    cin >> n >> m >> q;

    vector<bool> alive(n, true);
    list<int> list;
    FOR(i, 0, n)list.push_back(i);
    auto itr = list.begin();
    FOR(i, 0, m) {
        int a;
        cin >> a;
        if (a % 2 == 0) {
            FOR(j, 0, a) {
                itr++;
                if (itr == list.end())itr = list.begin();
            }
        }
        else {
            FOR(j, 0, a) {
                if (itr == list.begin())itr = list.end();
                itr--;
            }
        }
        alive[*itr] = false;
        itr = list.erase(itr);//消した要素の次のitrを返すっぽい
        if (itr == list.end())itr = list.begin();
    }

    while (q--) {
        int in;
        cin >> in;
        cout << alive[in] << "\n";
    }
}


Measured memory_bytes: 9436
#
# abc096 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
.#.
###
.#."""
        output = """Yes"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5 5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#"""
        output = """No"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """11 11
...#####...
.##.....##.
#..##.##..#
#..##.##..#
#.........#
#...###...#
.#########.
.#.#.#.#.#.
##.#.#.#.##
..##.#.##..
.##..#..##."""
        output = """Yes"""
        self.assertIO(input, output)


def resolve():
    H, W = map(int, input().split())
    S = [["."] * (W+2) for _ in range(H+2)]
    for i in range(H):
        S[i+1][1:W+1] = list(".") + list(input())

    ans = "Yes"
    for i in range(1, H+2):
        for j in range(1, W+2):
            if S[i][j] == "#":
                if S[i-1][j] == "." and S[i][j-1] == "." and S[i][j+1] == "." and S[i+1][j] == ".":
                    ans = "No"
                    break

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 16180
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>

typedef long long ll;
using namespace std;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;

const double EPS = 1e-8;

int main()
{
	int A,B;

	cin >> A >>B;

	if(A==1){A=14;}
	if(B==1){B=14;}

	if(A==B){
		cout << "Draw";
	}else if(A>B){
		cout << "Alice";
	}else{
		cout << "Bob";
	}
	return 0;
}


Measured memory_bytes: 256
exception Error of string
let err s = raise (Error s)

let _ =
    let w, h, x, y, r = Scanf.scanf "%d %d %d %d %d" (fun w h x y r -> w, h, x, y, r) in
    if r <= x && r <= y && x <= w-r && y <= h-r then print_endline "Yes"
    else print_endline "No"


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

typedef long long ll;

int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    if(a>b || (n==1 && a!=b))cout << 0 << endl;
    else if(n<3) cout << 1 << endl;
    else cout << (n-2)*(b-a)+1 << endl;
    return 0;
}


Measured memory_bytes: 256
use v6;

my ($n, $m, $x, $y) = +<<get.words;
my @xs = +<<get.words;
my @ys = +<<get.words;
my ($mx, $my) = @xs.max, @ys.min;
if $mx < $my && $x < $mx && $my < $y {
  say 'No War'
}
else {
  say 'War';
}


Measured memory_bytes: 61132
#include<bits/stdc++.h>
#define ll long long
#define db double
#define mod 1000000007
#define pb push_back
#define pp pair<ll,ll>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repe(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=b;i>=a;i--)
#define maxn 200005
#define ss second
#define ff first
#define lb lower_bound
using namespace std;
void solve()
{
    ll a,b,n;
    cin >> a >> b >> n;
    ll r2;
    if(n/b > 0)
    {
        r2=b-1;
    }
    else r2=n;
    ll q1 = a/b;
    ll r1 = a%b;
    q1 = (q1*r2)+((r1*r2)/b);
    cout << q1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}

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

int main() {
  int H, W;

  while (true) {
    cin >> H >> W;
    if (H == 0 && W == 0) break;
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        cout << '#';
      }
      cout << endl;
    }
    cout << endl;
  }
}


Measured memory_bytes: 3104
str = [w for w in input()]
q = int(input())
for i in range(q):
    command = [w for w in input().split()]
    command[1] = int(command[1])
    command[2] = int(command[2])
    if command[0] == "print":
        for i in range(command[1], command[2]+1):
            print(str[i], end="")
        print()
    if command[0] == "replace":
        j = command[1]
        for i in range(len(command[3])):
            str[j] = command[3][i]
            j += 1
    if command[0] == "reverse":
        r = []
        for i in range(command[2], command[1]-1, -1):
            r.append(str[i])
        i = command[1]
        for w in r:
            str[i] = w
            i += 1

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

using ll = long long;

const ll INF = 1001001001;
const ll mod = 1000000007;

int main() {
	int N;
	cin >> N;
	vector<double> p(N);
	for (int i = 0; i < N; ++i) cin >> p[i];
	vector<vector<double>> dp(N + 1, vector<double>(N + 1, 0));
	dp[0][0] = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N + 1; ++j) {
			if (j > 0) dp[i + 1][j] += p[i] * dp[i][j - 1];
			dp[i + 1][j] += (1 - p[i]) * dp[i][j];
		}
	}
	double ans = 0;
	for (int i = N/2 + 1; i <= N; ++i) ans += dp[N][i];
	printf("%.10f\n", ans);
}

Measured memory_bytes: 70656
n, m = map(int, input().split())
C = sorted([int(x) for x in input().split()])
dp = [int(x) for x in range(n + 1)]
for c in C[1:]:
    for i in range(n + 1):
        anc = i - c
        if anc < 0:
            continue
        dp[i] = min(dp[i], dp[anc] + 1)
print(dp[n])



Measured memory_bytes: 7472
import math
from collections import defaultdict

#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        factor.append(n)
        factor.append(1)
        return factor
    else:
        factor.append(n)
        return factor

N = int(input())
l = defaultdict(int)
for i in range(1,N+1):
    for j in trial_division(i):
        if j != 1:
            l[j] += 1

ans = 1
for i in list(l.values()):
    ans *= (i+1)

print(ans%(10**9+7))


Measured memory_bytes: 44012
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n); REP (i, n) scanf("%d", &a[i]);
    vector<int> b(n); REP (i, n) scanf("%d", &b[i]);
    vector<int> c(n); REP (i, n) scanf("%d", &c[i]);
    // solve
    sort(ALL(a));
    sort(ALL(b));
    sort(ALL(c));
    vector<ll> dp1(n); {
        int i = 0;
        REP (j, n) {
            while (i < n and a[i] < b[j]) ++ i;
            dp1[j] = i;
        }
        REP (j, n - 1) {
            dp1[j + 1] += dp1[j];
        }
    }
    vector<ll> dp2(n + 1); {
        int j = 0;
        REP (k, n) {
            while (j < n and b[j] < c[k]) ++ j;
            dp2[k] = (j == 0 ? 0 : dp1[j - 1]);
        }
    }
    ll result = accumulate(ALL(dp2), 0ll);
    // output
    printf("%lld\n", result);
    return 0;
}


Measured memory_bytes: 2944
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Vishal Burman
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ARegistration solver = new ARegistration();
        solver.solve(1, in, out);
        out.close();
    }

    static class ARegistration {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            String str = in.readLine();
            String str2 = in.readLine();
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) != str2.charAt(i)) {
                    out.println("No");
                    return;
                }
            }
            out.println("Yes");
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        private String readLine0() {
            StringBuilder buf = new StringBuilder();
            int c = read();
            while (c != '\n' && c != -1) {
                if (c != '\r') {
                    buf.appendCodePoint(c);
                }
                c = read();
            }
            return buf.toString();
        }

        public String readLine() {
            String s = readLine0();
            while (s.trim().length() == 0) {
                s = readLine0();
            }
            return s;
        }

    }
}



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

int main(){
    int n;
    cin >> n;
    //??´????????°?????¨?±?????????????????????????
    int apart[5][5][12] = {0};

    for(int i = 0; i < n; i++){
        int ren, kai, heya, hito = 0;
        cin >> ren >> kai >> heya >> hito;
        apart[ren][kai][heya] += hito;
    }

    for(int i = 1; i <= 4; i++){
        for(int j = 1; j <= 3; j++){
            for(int k = 1; k <= 10; k++){
                cout << " " << apart[i][j][k];
            }
            cout << endl;
        }
        if(i != 4)cout << "####################" << endl;
    }

return 0;
}

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

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

  int n; cin >> n;
  for(int i=0;i<n;i++) {
    string s1,s2;
    cin >> s1;
    cin >> s2;
    int s1_itr = s1.length() - 1;
    int s2_itr = s2.length() - 1;
    bool is_shift = false;
    int digit;
    vector<int> sum;
    while(s1_itr >= 0 || s2_itr >= 0) {
      digit = 0;
      if(s1_itr >= 0)
        digit += s1[s1_itr] - '0';
      if(s2_itr >= 0)
        digit += s2[s2_itr] - '0';
      if(is_shift)
        digit += 1;

      if(digit >= 10) {
        is_shift = true;
        digit = digit - 10;
      }
      else {
        is_shift = false;
      }
      sum.push_back(digit);
      s1_itr--;
      s2_itr--;
    }
    if(is_shift)
      sum.push_back(1);

    if(sum.size() > 80) {
      cout << "overflow" << endl;
    }
    else {
      for(int i=sum.size()-1;i>=0;i--) {
        cout << sum[i];
      }
      cout << endl;
    }
  }
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
#define itn int

int main(void){
    int n;
    cin >> n;
    
    map<int,int>mp;
    int a[n];
    for(int i = 0;i < n-1;i++){
        cin >> a[i];
        mp[a[i]]++;
    }
    
    for(int i = 1;i <= n;i++)cout << mp[i] << endl;
}

Measured memory_bytes: 13788
import java.util.*;public class Main{public static void main(String[] a){Scanner s=new Scanner(System.in);int n=s.nextInt();int[]p=new int[99];for(;n-->0;System.out.println(p['I']>>2))for(p['I']=0,p['U']=0;p['U']<3;){char c=s.next().charAt(1);p[c]++;if ((p[c]&3)==0)p[c]|=3;if(c=='O'){c='I';p[c]+=((p[c]&3)+1)<<2;p[c]&=~3;}}}}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
int main(){
  int r,d,x;
  cin>>r>>d>>x;
  int a[11];
  a[0]=x;
  rep(i,1,11)a[i]=r*a[i-1]-d;
  rep(i,1,11)cout<<a[i]<<endl;
}

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

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
 
ll a, b, c, d;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>a>>b>>c>>d;
	ll res = 0;
	res = max(a, b) * max(c, d);
	res = max(min(a, b) * min(c, d), res);
	res = max(min(a, b) * max(c, d), res);
	res = max(max(a, b) * min(c, d), res);
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 3648
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;

int main(){
  int n;
  cin >> n;
  vector<double> v(n);
  rep(i,n){
    cin >> v[i];
  }
  sort(v.begin(),v.end());
  double ans = 0;
  ans = (v[0]+v[1])/2;
  for(int i = 2; i <= n-1; i++){
    ans = (ans+v[i])/2;
  }
  printf("%lf\n", ans);
  return 0;
}


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

void solve()
{
  int N, K;
  cin >> N >> K;
  vector<int> nums;
  for (int i = 0; i < K; ++i)
  {
    int tmp;
    cin >> tmp;
    nums.push_back(tmp);
  }
  int i = 0;
  while (1)
  {
    int flag = 0;
    int tmp = N + i;
    string S = to_string(tmp);
    for (int j = 0; j < S.size(); ++j)
    {
      for (int k = 0; k < nums.size(); k++)
      {
        if (S[j]-'0' == nums[k])
        {
          flag = 1;
          break;
        }
      }
      if (flag)
        break;
    }
    if (flag==0)
    {
      cout << tmp << endl;
      break;
    }
    i++;
  }
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 3640
#pragma optimize("", off)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:36777216")
#include <bits/stdc++.h>

#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long 
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz(i) (int)(i.size())
#define setto(n) cout << fixed << setprecision(n)
#define fi first
#define se second
#define ld long double
#define inf LONG_MAX
#define pii pair<int, int>
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
const int mod = 1000000007;
using namespace std;

#define meta __FUNCTION__<<" : "<<__LINE__<<" "
#define tr1(x) cerr<<meta<<"| "<<#x<<" : "<<x<<" | "<<endl
#define tr2(x,y) cerr<<meta<<"| "<<#x<<" : "<<x<<" | "<<" "<<#y<<" : "<<y<<" | "<<endl
#define tr3(x,y,z) cerr<<meta<<"| "<<#x<<" : "<<x<<" | "<<" "<<#y<<" : "<<y<<" | "<<" "<<#z<<" : "<<z<<" | "<<endl
#define tr4(w,x,y,z) cerr<<meta<<"| "<<#w<<" : "<<w<<" | "<<" "<<#x<<" : " <<x<<" | "<<" "<<#y<<" : "<<y<<" | "<<" "<<#z<<" : "<<z<<" | "<<endl
#define tr5(v,w,x,y,z) cerr<<meta<<"| "<<#v<<" : "<<v<<" | "<<" "<<#w<<" : "<<w<<" | "<<" "<<#x<<" : "<<x<<" | "<<" "<<#y<<" : "<<y<<" | "<<" "<<#z<<" : "<<z<<" | "<<endl
#define tr6(u,v,w,x,y,z) cerr<<meta<<#u<<" : "<<u<<" | "<<" "<<#v<<" : "<<v<<" | "<<" "<<#w<<" : "<<w<<" | "<<" "<<#x<<" : "<<x<<" | "<<" "<<#y<<" : "<<y<<" | "<<" "<<#z<<" : "<<z<<" | "<<endl

template<class T> void smin(T& a, T val) {if (a > val) a = val;}
template<class T> void smax(T& a, T val) {if (a < val) a = val;}
template<typename T>inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v){bool first = true;os << "[";for(auto i: v){if(!first)os << ", ";os << i;first = false;}return os << "]";}
//Check N size twiceeeeeeeeeeeeeeeeee, and verify it

const int N = 1e7 + 10;

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

	int ans = 1;
	for (int i = 1; i*i <= m; i++)
	{
		// gcd is i
		if(m % i)continue;
		int tt = m/i;
		if(i >= n){
			smax(ans, tt);
		}
		if(tt >= n){
			smax(ans, i);
		}
	}

	cout<<ans;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int MAXN = 100010;
vector<int> Tree(MAXN, 0), Size(MAXN, 1);

void init(int N)
{
  for (int i = 1; i <= N; i++)
    Tree.at(i) = i;
}

int root(int x)
{
  if (Tree.at(x) == x)
    return x; // 根
  else
    return Tree.at(x) = root(Tree.at(x)); // 経路圧縮
}

void unite(int x, int y)
{
  x = root(x);
  y = root(y);
  if (x == y)
    return;
  Tree.at(x) = y;
  Size.at(x) = Size.at(x) + Size.at(y);
  Size.at(y) = Size.at(x);
}

int main()
{
  int64_t N, M, a, b, ans = 0, z = 0;
  cin >> N >> M;
  init(N);
  vector<pair<int64_t, int64_t>> vp;
  for (int i = 0; i < M; i++)
  {
    cin >> a >> b;
    vp.push_back(make_pair(a, b));
  }
  stack<int64_t> A;
  for (int i = M - 1; i >= 0; i--)
  {
    tie(a, b) = vp.at(i);
    int64_t prv_a = Size.at(root(a)), prv_b = Size.at(root(b));
    unite(a, b);
    int64_t prv = (prv_a * (prv_a - 1) / 2) + (prv_b * (prv_b - 1) / 2);
    int64_t s = Size.at(root(a));
    A.emplace(max(z, (s * (s - 1) / 2) - prv));
  }
  while (!A.empty())
  {
    ans += A.top();
    cout << ans << endl;
    A.pop();
  }
}

Measured memory_bytes: 4464
#include <bits/stdc++.h>
using namespace std;
int n,m,cnt; 
vector<int>g[100004];
int vis[100004];
int main(){
	cin>>n>>m;
	memset(vis,-1,sizeof(vis));
	for(int i=0;i<m;i++){
		int u,v;cin>>u>>v;
		g[u].push_back(v),g[v].push_back(u);
	}
	queue<int>q;
	q.push(1);
	cnt=1;
	while(!q.empty()){
		int x=q.front();cnt++;q.pop();
		for(int i=0;i<g[x].size();i++)if(vis[g[x][i]]<0)
			q.push(g[x][i]),vis[g[x][i]]=x;
	}
	if(cnt<n)puts("No");
	else{
		puts("Yes");
	for(int i=2;i<=n;i++)cout<<vis[i]<<"\n";
}
}

Measured memory_bytes: 10512
n,a,b,*H=map(int,open(0).read().split())
l,r=0,10**9
while r-l>1:
	x=0;m=(l+r)//2
	for h in H:
		x-=min(0,(h-m*b)//(b-a))
	if x>m:
		l=m
	else:
		r=m
print(r)

Measured memory_bytes: 14092
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 105
using namespace std;
typedef long long ll;
int h,w,ans;
char s[maxn][maxn];
bool vis[maxn][maxn];
const int dx[] = {0,-1,0,1};
const int dy[] = {-1,0,1,0};
void dfs(int x,int y){
	vis[x][y] = true;
	for(int i=0;i<4;i++){
		int cx = x + dx[i];
		int cy = y + dy[i];
		if(cx >= 1 && cx <= h && cy >= 1 && cy <= w && !vis[cx][cy] && s[cx][cy] == s[x][y]) dfs(cx,cy);
	}
}
int main(){
	while(~scanf("%d%d",&h,&w) && h){
		for(int i=1;i<=h;i++) scanf("%s",s[i] + 1);
		memset(vis,0,sizeof(vis));
		ans = 0;
		for(int i=1;i<=h;i++){
			for(int j=1;j<=w;j++){
				if(!vis[i][j]){
					ans++;
					dfs(i,j);
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}



Measured memory_bytes: 3904
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use proconio::*;
use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    input! {
        n:usize,
        a:[usize;n],
    }

    const MAX_NUM: usize = 1000000;
    let mut g = 0;
    // let is_set_wise = a.iter().fold(0, |acc, ai| acc.gcd(ai)) == 1;

    let era = Eratosthenes::new(MAX_NUM);
    let mut divisor_counter = [0; MAX_NUM + 1];

    let mut flag = false;

    for ai in a {
        g = g.gcd(&ai);

        let hm = era.factorization(ai);

        for (k, _v) in hm {
            divisor_counter[k] += 1;
            if divisor_counter[k] >= 2 {
                flag = true;
                break;
            }
        }
    }

    let is_set_wise = g == 1;

    let ans = if !flag {
        "pairwise coprime"
    } else if is_set_wise {
        "setwise coprime"
    } else {
        "not coprime"
    };

    println!("{}", ans);
}

use itertools::Itertools;
use num::Integer;
use rustc_hash::FxHashMap;
use smallvec::alloc::collections::BTreeMap;
use std::collections::HashMap;
use std::mem::swap;

/// 二分累乗法
pub fn pow(x: isize, n: usize) -> isize {
    if n == 0 {
        1
    } else if n == 1 {
        x
    } else if n % 2 == 1 {
        x * pow(x, n - 1)
    } else {
        pow(x * x, n / 2)
    }
}

/// エラトステネスの篩
/// 構築 O(N log log N)
/// 素因数分解 O(log N)
/// 素数判定 O(log N)
pub struct Eratosthenes {
    smallest_prime_factors: Vec<usize>,
}

impl Eratosthenes {
    pub fn new(n: usize) -> Self {
        let mut smallest_prime_factors = (0..=n).collect_vec();

        for i in 2..n {
            if i * i > n {
                break;
            }

            if smallest_prime_factors[i] != i {
                continue;
            }

            let mut j = i * i;
            while j <= n {
                if smallest_prime_factors[j] == j {
                    smallest_prime_factors[j] = i;
                }

                j += i;
            }
        }

        Self {
            smallest_prime_factors,
        }
    }

    pub fn factorization(&self, mut i: usize) ->BTreeMap<usize, usize> {
        assert_ne!(i, 0);

        let mut factors = BTreeMap::default();

        while i != 1 {
            let divisor = self.smallest_prime_factors[i];
            *factors.entry(divisor).or_insert(0) += 1;

            i /= divisor;
        }

        factors
    }

    pub fn is_prime(&self, i: usize) -> bool {
        i >= 2 && self.smallest_prime_factors[i] == i
    }
}


Measured memory_bytes: 29200
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
ans = 0
v = a[0]
for i in range(1,n):
    if a[i]<v:
        ans += v-a[i]
    else:
        v = a[i]
print(ans)

Measured memory_bytes: 105148
using System;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using LayoutKind = System.Runtime.InteropServices.LayoutKind;
using StructLayoutAttribute = System.Runtime.InteropServices.StructLayoutAttribute;
using FieldOffsetAttribute = System.Runtime.InteropServices.FieldOffsetAttribute;


static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var v = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var c = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(v.Zip(c,(x,y) => x - y).Where(x => x >= 0).Sum());
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for(int i=m; i<n; i++)
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
template <typename T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0; }
template <typename T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1;} return 0; }

ll a[200001];
ll S[200010];
ll ans[2019];
int main() {
    string s; cin>>s;
    reverse(s.begin(),s.end());
    int j=1;
    rep(i,0,s.size()){
        j%=2019;
        a[i]=s[i]-'0';
        a[i]*=j;
        a[i]%=2019;
        j*=10;
        S[i+1]+=a[i]+S[i];
        S[i+1]%=2019;
    }
    //rep(i,0,s.size()+1) cout<<S[i]<<" ";
    
    
    rep(i,0,s.size()+1){
        ans[S[i]]++;
    }
    ll res=0;
    rep(i,0,2019){
        res+=ans[i]*(ans[i]-1)/2;
    }
    cout<<res<<endl;
    
}

Measured memory_bytes: 6824
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <cassert>
#include <queue>
#include <random>
#include <stack>
#include <iomanip>

using namespace std;

typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;
typedef long double ldouble;

typedef vector<llong> vecllong;
typedef vector<vecllong> vvecllong;

const llong MOD = 1e9 + 7;
const llong INF = 1e17;

#define FOR(i, n) for (llong i = 0; i < n; i++)
#define FORS(i, a, b) for (llong i = a; i < b; i++)
#define FORR(i, n) for (llong i = n; i > 0; i++)

int main(void) {
    llong N;
    cin >> N;

    vecllong primes(1, 2);
    llong count = 0;

    for(llong i = 7; i <= 55555; i++) {
        bool isPrime = [] (llong integer, vecllong primes) {
            for(llong i = 0; i < primes.size(); i++) {
                if (integer % primes[i] == 0) {
                    return false;
                }
            }
            return true;
        }(i, primes);

        if (isPrime) {
            primes.push_back(i);
            if (i % 5 == 1) {
                cout << i << " ";
                count++;
                if (count >= N) {
                    break;
                }
            }
        }
    }

    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
#define M 1000000007
#define pie 3.141592653589793238
using namespace std;


signed main(){  
    int n; cin >> n;
    map<int,int> m;
    vector<int> v;
    int a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
        if(m[a[i]] == 0){
            v.push_back(a[i]);
        }
        m[a[i]]++;
    }
    sort(v.begin(), v.end());
    int ans = 0;
    n = v.size();
    for(int i=0; i<n-2; i++){
        for(int j=i+1; j<n-1; j++){
            for(int k=j+1; k<n; k++){
                if((v[i]+v[j]) > v[k] && (v[i]+v[k]) > v[j] && (v[k]+v[j]) > v[i]){
                    ans += (m[v[i]]*m[v[j]]*m[v[k]]);
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3632
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def uy():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

n,m = uy()

a = l()

su = 0
for i in range(n+1):
	ll = max(i,n-(m - i))
	if ll == i:
		lll = abs(i-n-(m - i))
	else:
		lll = 0

	for j in range(ll,n+1):
		q = []
		co = 0
		p = a[:i]
		pp = a[j:]
		for k in range(len(p)):
			if p[k] < 0:
				hq.heappush(q,p[k])
		for k in range(len(pp)):
			if pp[k] < 0:
				hq.heappush(q,pp[k])
		co += sum(p)
		co += sum(pp)
		q.sort()
		for k in range(min(len(q),j-ll+lll)):
			co += abs(hq.heappop(q))
		su = max(su,co)
print(su)


Measured memory_bytes: 3436
#include<iostream>
#include<string>

using namespace std;

int main(void) {
	string s;
	int a, b;
	bool flag = true;

	cin >> a >> b;
	cin >> s;

	for (int i = 0; i < s.size(); i++) {
		if (i == a) {
			if (s[i] != '-') {
				flag = false;
			}
		}
		else {
			if (s[i] == '-') {
				flag = false;
			}
		}
	}

	if (flag) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
  
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>

#include "atcoder/convolution.hpp"
#include "atcoder/dsu.hpp"
#include "atcoder/fenwicktree.hpp"
#include "atcoder/lazysegtree.hpp"
#include "atcoder/math.hpp"
#include "atcoder/maxflow.hpp"
#include "atcoder/mincostflow.hpp"
#include "atcoder/modint.hpp"
#include "atcoder/scc.hpp"
#include "atcoder/segtree.hpp"
#include "atcoder/string.hpp"
#include "atcoder/twosat.hpp"

#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define rank qwertyuio
#define next dfghjk
#define prev fhsgfhjf
#define plus fsghsf
#define minus ytryr
  
using namespace std;
using namespace atcoder;
  
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  
const int N = 100000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD2 = 998244353;
const ld eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;

ll gcd_ex(ll a, ll b, ll &x, ll &y) // a * x + b * y = gcd(a, b)
{
    if (a == 0)
    {
        x = 0; y = 1;
        return b;
    }
    ll x1, y1;
    ll d = gcd_ex(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

ll solve(ll n1, ll n2) {
    ll x, y;
    ll g = gcd_ex(n1, n2, x, y);
    if (g != 1) {
        return big;
    }
    y %= n1;
    if (y < 0) {
        y += n1;
    }
    if (y * n2 <= 1) {
        y += n1;
    }
    return y * n2 - 1;
}

int main()
{
    //freopen("circus.in", "r", stdin);
    //freopen("circus.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    //ll TL = 10.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    ll n;
    cin >> n;
    n *= 2;
    ll ans = big;
    for (ll x = 1; x * x <= n; x++) {
        if (n % x == 0) {
            setmin(ans, solve(x, n / x));
            setmin(ans, solve(n / x, x));
        }
    }
    cout << ans << "\n";
    return 0;
}



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

void solve(long long X){
    cout << 8-((X-400)/200) << endl;

}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long X;
    scanf("%lld",&X);
    solve(X);
    return 0;
}


Measured memory_bytes: 3760
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)

    if i != len(a) and a[i] == x:
        return i
    raise ValueError

# ポイント
# 文字列update
# 文字種の高速取得

# 文字種の高速取得について考えてみる
# 文字のidxを取得しておいて二分探索することで高速に取得することが可能


N = read_a_int()
S = list(read()[:-1])

from collections import defaultdict
from bisect import bisect_left, bisect_right, insort_left
char_idxs = defaultdict(lambda: [])
for i, s in enumerate(S):
    char_idxs[s].append(i)


def get_syurui(char_idxs, l, r):
    ret = 0
    for v in char_idxs.values():
        l_idx = bisect_left(v, l)
        r_idx = bisect_right(v, r)
        # print(v,l_idx,r_idx)
        if r_idx - l_idx > 0:
            ret += 1
    return ret


Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 2:
        a, b = int(a) - 1, int(b) - 1
        print(get_syurui(char_idxs, a, b))
    else:
        i = int(a) - 1
        if S[i] == b:
            continue
        # i文字目を消す
        tmp = char_idxs[S[i]]  # S[i]を更新しなきゃ
        del char_idxs[S[i]][index(tmp, i)]
        # cのidxに挿入し直す
        insort_left(char_idxs[b], i)
        # S[i]を更新しなきゃ
        S[i] = b


Measured memory_bytes: 31348
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

int main(){
  int a,b,c;
  cin >> a >> b>> c;
  if(b-a == c-b){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import statistics
import string
import sys
from array import array
from collections import deque

def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)


N = intinput()
dic = {}
ans = 0
true_person = 0
flag_contradiction = 0
for i in range(N):
    dic[i] = {}

for i in range(N):
    A = intinput()
    for j in range(A):
        x,y = splitintinput()
        dic[i][x-1] = y

for i in range(2**N):
    tmp = format(i, 'b').zfill(N)
    true_person = tmp.count('1')
    flag_contradiction = 0
    for j in range(N):
        if int(tmp[j]) == 1:
            for k in dic[j]:
                if dic[j][k] != int(tmp[k]):
                    flag_contradiction = 1
                    break
    if flag_contradiction == 0:
        ans = max(ans,true_person)

print(ans)



Measured memory_bytes: 5532
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <stack>
using namespace std;
typedef long long int ll;
const ll  MOD = 1000000007;
typedef pair<ll,ll> P;

ll N;
ll a[1010];
ll ans=1;
int main(){
  cin >> N;
  for(int i=2;i<=N;i++){
    ll t = i;
    for(int j=2;j<=N;j++){
      if(i<j) break;
      while(t%j == 0){
        a[j]++;
        t/=j;
      }
    }
  }
  for(int i=2;i<=N;i++){
    ans = (ans*(a[i]+1)) % MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int m,x,y,i;
  scanf("%d%d",&x,&y);
  if(x==y){
    printf("%d\n",x);
    return 0;
  }
  
  m=x<y?y%x:x%y;
  y=x>y?y:x;
  for(i=m;i>0;i--){
    
    if(m%i==0&&y%i==0){
      printf("%d\n",i);
    return 0;
    }
  }

  return 0;
}
    
  


Measured memory_bytes: 2048
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
lint a[100100];
lint rma[100100],rmi[100100],ma[100100],mi[100100],out[100100];
lint inf=1E18;
lint cal(){
	int n;cin>>n;rep(i,n+1) cin>>a[i];
	rma[0]=1;
	rep(i,n+10){
		rma[i+1]=min(inf,(rma[i]-a[i])*2);
	}
	ma[n]=mi[n]=a[n];
	for(int i=n;i>0;i--){
		mi[i-1]=a[i-1]+(mi[i]+1)/2;
		ma[i-1]=a[i-1]+ma[i];
	}
	lint ret=0;
	rep(i,n+1){
		if(mi[i]>rma[i]) return -1;
		ret+=min(rma[i],ma[i]);
		out[i]=min(rma[i],ma[i]);
	}
	rep(i,n){
		//cout<<out[i]<<endl;
		assert(out[i+1]>=out[i]-a[i] && out[i+1]<=(out[i]-a[i])*2);
	}
	return ret;
}
int main()
{
	cout<<cal()<<endl;
}


Measured memory_bytes: 7520
n = int(input())
a_list = [int(x) for x in input().split()]
if n % 2 == 0:
    b_list = a_list[n-1::-2] + a_list[0::2]
else:
    b_list = a_list[n-1::-2] + a_list[1::2]
print(*b_list)

Measured memory_bytes: 30804
/*
   first we need to sort the all edges then updates them one after another .
   we update them according to the adjacent edges then maximize the answer of edge
*/
#include<queue>
#include<map>
#include <string>
#include<bits/stdc++.h>
#define pi 3.141592654
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define input ios_base::sync_with_stdio(0);cin.tie(0);
//#define x real()
//#define y imag()
using namespace std;
typedef pair<double,double>pdd;
typedef long long  ll;
typedef pair<ll, ll>pii;
//typedef complex<double> point;
//template<typename T>T gcd(T x, T y) { if(y == 0)return x; else return gcd(y, x%y); }
//typedef bitset<30> mask;
//int x[8]={1,0,0,-1,-1,-1,1,1};
//int y[8]={0,1,-1,0,-1,1,-1,1};
//#define var(x) ((x)<<1)
//#define nvar(x) ((x)^1)
ll r,d,x,a,b;
 main()
{

//cout<<Pow((ll)1000000,(ll)110);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//    char input[15];
//    scanf("%s", &input);  array of char
//  gets(c+1);  array of char
//printf("%s, ",name[k[i]].c_str());  printf of string
input;

cin>>r>>d>>x;
forr(i,1,10)
{
    cout<<x*r-d<<endl;
    x=x*r-d;
}
return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	long long int dp[105][41]={0};
	int i,j,N,a;
	scanf("%d",&N);
	scanf("%d",&a);
	dp[1][10+a]=1;
	for(i=2;i<N;i++){
		scanf("%d",&a);
		for(j=10;j<=30;j++){
			dp[i][j]=dp[i-1][j+a]+dp[i-1][j-a];
		}
	}
	scanf("%d",&a);
	printf("%lld\n",dp[N-1][10+a]);
	return 0;
}

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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, r;
    cin >> n >> r;

    if (n < 10)
        cout << r + 100 * (10 - n) << "\n";
    else
        cout << r << "\n";

    return 0;
}


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

using namespace std;

main () {
  string s; cin >> s;
  int n = s.size();
  int r = 0;
  int p = 0;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'g') {
      if (p + 1 <= r) {
        ans++;
        p++;
      } else r++;
    } else {
      if (p + 1 <= r) {
        p++;
      } else {
        r++;
        ans--;
      }
    }
  }
  cout << ans;
}


Measured memory_bytes: 512
import sys
input = sys.stdin.readline
from collections import *

def judge(x):
    d = defaultdict(int)
    
    for i in range(N-x+1):
        k = S[i:i+x]
        
        if k in d:
            if i>=d[k]+x:
                return True
        else:
            d[k] = i
    
    return False

def binary_search():
    l, r = 0, N
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            l = m+1
        else:
            r = m-1
    
    return r

N = int(input())
S = input()[:-1]
print(binary_search())


Measured memory_bytes: 157448
// Problem : B - 81
// Contest : AtCoder Beginner Contest 144
// URL : https://atcoder.jp/contests/abc144/tasks/abc144_b
// Memory Limit : 1024,000000 MB
// Time Limit : 2000,000000 milisec
// Powered by CP Editor (https://github.com/coder3101/cp-editor2)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main() {
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cout.precision(16);
  cout << fixed;

  int n;
  cin >> n;

  for (int i = 1; i < 10; ++i) {
    for (int j = 1; j < 10; ++j) {
      if (i * j == n) {
        cout << "Yes";
        
        return 0;
      }
    }
  }

  cout << "No";
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
count = 0
check = 1
for i in range(len(a)):
    if a[i] == check:
        check += 1
    elif a[i] != check:
        count += 1
if count == len(a):
    print(-1)
else:
    print(count)

Measured memory_bytes: 77644