akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-


def bubbleSort(A, N):

    flag = True  # 未ソートの可能性があるか
    i = 0  # 未ソート部分の先頭
    inv_num = 0  # 転倒数
    while flag:
        flag = False
        for j in range(N - 1, i, -1):
            if A[j][1] < A[j - 1][1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                flag = True
                inv_num += 1
        i += 1

    return A, inv_num


def selectionSort(A, N):
    count = 0

    for i in range(N):

        minj = i
        for j in range(i, N):
            if A[j][1] < A[minj][1]:
                minj = j
        if minj != i:
            count += 1

        A[i], A[minj] = A[minj], A[i]

    return A, count


if __name__ == '__main__':

    N = int(input())
    A = [(a[0], int(a[1])) for a in input().split(" ")]

    A_bubble, _ = bubbleSort(A.copy(), N)
    A_selection, _ = selectionSort(A.copy(), N)

    A_bubble = [a[0] + str(a[1]) for a in A_bubble]
    A_selection = [a[0] + str(a[1]) for a in A_selection]

    print(' '.join(A_bubble))
    print("Stable")
    print(" ".join(A_selection))
    if A_selection == A_bubble:
        print("Stable")
    else:
        print("Not stable")



Measured memory_bytes: 5620
#include <stdio.h>

int binarysearch (int key, int n, int a[]) {
    int left = 0;
    int right = n;
    int mid;

    while ( left < right ) {
        mid = (left + right) / 2;
        if ( a[mid] == key ) {
            return 1;
        }
        else if ( key < a[mid] ) {
            right = mid;
        }
        else
            left = mid + 1;
        }
        return 0;
    }

int main () {
    int n, q, i, key;
    int s[200000];
    int c = 0;
    
    scanf("%d", &n);
    for ( i = 0; i < n; i++ ) {
        scanf("%d", &s[i]);
    }

    scanf("%d", &q);
    for ( i = 0; i < q; i++ ) {
        scanf("%d", &key);
        if ( binarysearch(key, n, s) )
        c++;
        }
    
    printf("%d\n", c);

    return 0;
}


Measured memory_bytes: 2112
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

Acum = [0]
for a in A:
    Acum.append(Acum[-1] + a)

c = Counter(Acum)
ans = sum(x * (x - 1) // 2 for x in c.values())
print(ans)


Measured memory_bytes: 41728
#include <math.h>
#include <utility>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main(){

	bool f = false;
	while(true) {

		int n;
		cin >> n;
		if ( n == 0 ) break;
		if ( f ) cout << endl;

		vector<string> country;
		vector<int> score;
		string input1;
		int input2,input3,input4;
		vector<bool> flag;

		for ( int i = 0; i < n; i++ ) {

			int cnt = 0;
			cin >> input1 >> input2 >> input3 >> input4;
			country.push_back(input1);
			cnt += ( input2*3 + input4 ) * 10 + ( 9 - i );
			score.push_back(cnt);
			flag.push_back(true);

		}

		sort( score.begin(), score.end() );
		for ( int i = n-1; i >= 0; i-- ) {
			cout << country[ 9 - score[i]%10 ] << "," << score[i]/10 << endl;
		}
		f = true;
	}
	return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
int a[maxn][maxn],val[maxn][maxn],N;
void update(int x,int y)
{
  if(x == 0 || y == 0 || x == N+1 || y == N+1) return;
  int tmp = min(min(val[x+1][y],val[x-1][y]), min(val[x][y-1],val[x][y+1])) + a[x][y];
  if(tmp != val[x][y])
  {
    val[x][y] = tmp;
    update(x+1,y);
    update(x-1,y);
    update(x,y+1);
    update(x,y-1);
  }
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N;
  for(int i = 1; i <= N; i++)
  for(int j = 1; j <= N; j++)
  {
    a[i][j] = 1;
    val[i][j] = min(min(i,N-i+1),min(j,N-j+1));
  }
  int ans = 0;
  for(int i = 0; i < N*N; i++)
  {
    int data;
    cin >> data;
    data += N-1;
    int x = data / N, y = data%N + 1;
    ans += val[x][y]-1;
    a[x][y] = 0;
    update(x,y);
  }
  cout << ans << endl;
}


Measured memory_bytes: 32100
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

ld dp[305][305][305];

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	int cnt[4] = {0};
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		cnt[x]++;
	}
	for(int k = 0; k <= cnt[3]; k++) {
		for(int j = 0; j <= cnt[2] + cnt[3]; j++) {
			for(int i = 0; i <= n; i++) {
				if(i + j + k == 0) {
					dp[i][j][k] = 0;
				}
				else {
					dp[i][j][k] = 1;
					if(i >= 1) {
						dp[i][j][k] += (1.0 * i / n) * dp[i - 1][j][k];
					}
					if(j >= 1) {
						dp[i][j][k] += (1.0 * j / n) * dp[i + 1][j - 1][k];
					}
					if(k >= 1) {
						dp[i][j][k] += (1.0 * k / n) * dp[i][j + 1][k - 1];
					}
					dp[i][j][k] /= (1 - (1.0 * (n - i - j - k) / n));
				}
			}
		}
	}
	cout << fixed << setprecision(12) << dp[cnt[1]][cnt[2]][cnt[3]];

	return 0;
}

Measured memory_bytes: 436692
#include <bits/stdc++.h>
#define INF 1000000009
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[100005];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int dp[100005];
	fill(dp,dp+n,INF);
	for(int i=0;i<n;i++){
		*lower_bound(dp,dp+n,a[i])=a[i];
	}
	cout<<lower_bound(dp,dp+n,INF)-dp<<endl;
	return 0;
}


Measured memory_bytes: 3836
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N = 3005;
double p[MAX_N],dp[MAX_N][MAX_N];

int main()
{
	int N;
	cin >> N;
	rep(i,N)
	{
		cin >> p[i];
	}

	dp[0][0] = 1.0-p[0];
	dp[1][0] = p[0];
	rep(j,N-1)
	{
		rep(i,N+1)
		{
			dp[i][j+1] += dp[i][j] * (1-p[j+1]);
			dp[i+1][j+1] += dp[i][j] * p[j+1];
		}
	}
	/*
	rep(i,N+1)
	{
		rep(j,N)
		{
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	*/
	double ans = 0.0;
	int temp = N;
	while(temp*2 > N)
	{
		ans += dp[temp][N-1];
		temp--;
	}
	cout << setprecision(10) << ans << endl;
	return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;

int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    ll sum = 0;
    rep(i, n) sum ^= a[i];
    rep(i, n) {
        ll ans = sum ^ a[i];
        cout << ans << ' ';
    }
    cout << endl;
}


Measured memory_bytes: 4660
k = int(input())
m = [False] * k
s = 0
d = 7 % k
i = 0
while True:
  s = (s + d) % k
  d = d * 10 % k
  i += 1
  if s == 0:
    print(i)
    break
  if m[s]:
    print(-1)
    break
  m[s] = True


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

int main() {
  long N, K;
  cin >> N >> K;
  vector<long> A(N);
  for (long i = 0; i < N; i++) cin >> A.at(i);
  for (long i = K; i < N; i++) {
    cout << ((A.at(i) > A.at(i - K)) ? "Yes" : "No") << "\n";
  }
}

Measured memory_bytes: 4796
N=int(input())
A=list(map(int,input().split()))
A.sort()
if N % 2 == 0:
  for i in range(1,N,2):
    for n in range(2):
      if not A[i + n - 1] == i:
        print(0)
        exit()
  print(2**(N//2)%1000000007)
else:
  for i in range(0,N-1,2):
      for n in range(2):
        if i == 0 and n == 0:
          continue
        if not A[i + n - 1] == i:
          print(0)
          exit()
  print(2**((N-1)//2)%1000000007)

Measured memory_bytes: 14008
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
static const int N = 100;
int min(int,int);
int main(){
  int n,i,j,k,l;
  int p[N+1], m[N+1][N+1];

  scanf("%d",&n);

  for(i = 1; i <= n; i++){
    scanf("%d %d",&p[i-1],&p[i]);
  }


  for(i = 1; i <= n; i++)
    m[i][i] = 0;
  for(l = 2; l <= n; l++){
    for(i = 1; i <= n-l+1; i++){
      j = i + l - 1;
      m[i][j] = INT_MAX;
      for(k = i; k <= j-1; k++){
	m[i][j] = min(m[i][j],(m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]));
      }
    }
  }

  printf("%d\n",m[1][n]);
  
  return 0;
}

int min(int a, int b){
  if(a < b)
    return a;
  else
    return b;
}



Measured memory_bytes: 2104
/*
  author: ruruvuvu
  GitHub account: colon-ku

  created at: 2020-01-04 16:14:23
*/

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()
#define rep(x, y) for (int x = 0; x < y; x++)
#define MOD 1000000007

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

ostringstream oss_global;
string s_global = oss_global.str();

int main()
{
    int a, b;
    cin >> a >> b;

    cout << a*b - a - b + 1 << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
Alist = [0] + list(map(int,input().split()))
Sumlist = [0]*(N+1)
A = Alist[0]
Sumlist[0] = A
for i in range(1,N+1):
    Sumlist[i] = Sumlist[i-1] + Alist[i]
    Alist[i] = A ^ Alist[i]
    A = Alist[i]
Ans = 0
ri = 0
for le in range(N+1):
    while ri <= N and Sumlist[ri] - Sumlist[le] == Alist[le] ^ Alist[ri]:
        ri += 1
    Ans += ri-le-1
    if le == ri:
        ri += 1
print(Ans)

Measured memory_bytes: 32132
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

N, M = map(int, input().split())
ablist = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for index, ab in enumerate(ablist):
        a, b = ab
        if index != i:
            uf.union(a-1, b-1)
    if uf.group_count() >= 2:
        ans += 1
print(ans)


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

typedef long long ll;
typedef pair<int, int> ii;

int MOD = 1e9 + 7;
int INF = 1e9;
// ll INF = 1e18;

int n, m;
int fact[100005];

int solve(){
	cin >> n >> m;
	if(n > m) swap(n, m);
	fact[0] = 1; for(int i=1;i<=m;i++) fact[i] = 1LL * i * fact[i-1] % MOD;
	if(m - n > 1)
		cout << 0 << endl;
	else if(m - n == 1){
		cout << 1LL * fact[m] * fact[n] % MOD << endl;
	}else{
		cout << 2LL * fact[m] * fact[n] % MOD << endl;
	}

	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	// int t; cin >> t; while(t--)
	solve();
	// cout << (solve() ? "YES" : "NO") << endl;
	return 0;
}


Measured memory_bytes: 640
// 解答不能.
// foryou1006ll氏.
// https://atcoder.jp/contests/abc157/submissions/10562367
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const double eps = 1e-6;
vector<tuple<int, int, int>> info;

double nth_distance(double x, double y, int N, int K){
    vector<double> dist(N);
    rep(i, N) dist[i] = get<2>(info[i]) * hypot(x - get<0>(info[i]), y - get<1>(info[i]));
    nth_element(dist.begin(), dist.begin() + K - 1, dist.end());
    return dist[K - 1];
}

double nth_distance_lb(double x, double y, double r, int N, int K){
    vector<double> dist(N);
    rep(i, N){
        dist[i] = get<2>(info[i]) * hypot(max(abs(x - get<0>(info[i])) - r, 0.0), max(abs(y - get<1>(info[i])) - r, 0.0));
    }
    nth_element(dist.begin(), dist.begin() + K - 1, dist.end());
    return dist[K - 1];
}

int main(){
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N){
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        info.emplace_back(x, y, c);
    }
    double ans = 1e9;
    queue<tuple<double, double, double>> q;
    q.emplace(0, 0, 1000);
    while(!q.empty()){
        double x, y, r;
        tie(x, y, r) = q.front();
        q.pop();
        double lb = nth_distance_lb(x, y, r, N, K);
        if(ans - lb > eps * max(1.0, lb)){
            ans = min(ans, nth_distance(x, y, N, K));
            for(double dx : {-0.5, 0.5}){
                for(double dy : {-0.5, 0.5}){
                    q.emplace(x + dx * r, y + dy * r, r / 2.0);
                }
            }
        }
    }
    printf("%.15lf\n", ans);
    return 0;
}

Measured memory_bytes: 384
n, m = map(int, input().split())
ai = list(map(int, input().split()))

#print(ai)
#ais = sorted(ai, reverse=True)
ais = sorted(ai)
#print(ais)
dica={}
for i in range(len(ais)):
    dica.setdefault(i,ais[i])
#print(dica)

bc = []
for i in range(m):
    bc.append(list(map(int, input().split())))

#print(bc)
bcs = sorted(bc, reverse=True, key=lambda x:x[1])
#print(bcs)

pt = 0
for i in range(m):
    tn, tv =bcs[i]
    #print(pt, n)
    #print(dica)
    for j in range(pt,n):
        if dica[j] < tv and 0 < tn:
            dica[j]=tv
            tn=tn-1
            pt=j+1
        else:
            break

#print(ais)
print(sum(dica.values()))

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

int main() {
  long long N,X;
  cin >> N >> X;
  vector<long long> b(N),l(N),u(N);
  vector<pair<long long,long long>> ga(N);
  long long ans = 0;
  long long req = 0;
  for (int i=0; i<N; i++) {
    cin >> b[i] >> l[i] >> u[i];
    req += b[i] * l[i];
    ga[i].first = b[i] * l[i] + (X - b[i]) * u[i];
    ga[i].second = i;
  }
  sort(ga.begin(),ga.end());
  reverse(ga.begin(),ga.end());
  int now = 0;
  while (ga[now].first <= req) {
    ans += X;
    req -= ga[now].first;
    now++;
    if (now == N) {
      break;
    }
  }
  if (req == 0) {
    cout << ans << endl;
    return 0;
  }
  long long term = X;
  int nu;
  for (int i=0; i<N; i++) {
    if (ga[i].first > ga[now].first) {
      nu = ga[i].second;
      req += ga[i].first;
      req -= ga[now].first;
      if (b[nu] * l[nu] >= req) {
        term = min(term,(req - 1) / l[nu] + 1);
      }
      else {
        term = min(term,b[nu] + (req - b[nu] * l[nu] - 1) / u[nu] + 1);
      }
      
      req -= ga[i].first;
      req += ga[now].first;
      continue;
    }
    if (ga[i].first <= req) {
      break;
    }
    nu = ga[i].second;
    if (b[nu] * l[nu] >= req) {
      term = min(term,(req - 1) / l[nu] + 1);
    }
    else {
      term = min(term,b[nu] + (req - b[nu] * l[nu] - 1) / u[nu] + 1);
    }
  }
  
  cout << ans + term << endl;
}

Measured memory_bytes: 4224
let countUp a b c x =
  [
    for l in [|0..a|] do
    for m in [|0..b|] do
    for n in [|0..c|] do
    yield 500*l + 100*m + 50*n
  ]
  |> List.sumBy (fun v -> if v=x then 1 else 0)

let a = stdin.ReadLine() |> int
let b = stdin.ReadLine() |> int
let c = stdin.ReadLine() |> int
let x = stdin.ReadLine() |> int

printfn "%d" <| (countUp a b c x)

Measured memory_bytes: 18516
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
int main()
{
    int N, sum = 0;
    cin >> N;
    vector<int> s(N);
    rep(i, N) {
        cin >> s[i];
        sum += s[i];
    }

    if (sum % 10) cout << sum << endl;
    else {
        sort(all(s));
        rep(i, N) {
            if (s[i] % 10) {
                sum -= s[i];
                break;
            }
        }
        if (sum % 10) cout << sum << endl;
        else cout << 0 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <string.h>
#include <stdio.h>

int main()
{
	int i;
	int len;
	char str[20],copy[20];
	scanf("%s",str);
	len = strlen(str);
	for(i = 0; i < len; i++){
		copy[len - i - 1] = str[i];
	}
	for(i = 0; i < len; i++){
		str[i] = copy[i];
	}
	printf("%s\n",str);
	return 0;
}

Measured memory_bytes: 944
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) (bit>>(i)) & 1
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define ENDL cout << endl;
using namespace std;
using LL = long long;
using LD = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using PLL = pair<LL, LL>;
using VPLL = vector<PLL>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
using VD = vector<double>;
const LL INF = 1e18;
const LL MOD = 1e9 + 7;

template<class T> inline bool chmin(T &a, T b){if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){if (a < b) {a = b; return true;} return false;}

void END(){cout << 1 << endl; exit(0);}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  if (a != 1 && b != 1) cout << 1 << endl;
  else if (a != 2 && b != 2) cout << 2 << endl;
  else if (a != 3 && b != 3) cout << 3 << endl;

  return 0;
}


Measured memory_bytes: 256
*S, = map(ord, input())
*T, = map(ord, input())
LS = len(S); LT = len(T)

dp = [[-1]*(LT+1) for i in range(LS+1)]
for i in range(LS-1, -1, -1):
    for j in range(LT-1, -1, -1):
        if S[i] == T[j]:
            dp[i][j] = max(dp[i+1][j+1] + 1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j+1])
i = j = 0
ans = []
while i < LS and j < LT:
    if S[i] == T[j]:
        if dp[i][j] == dp[i+1][j+1] + 1:
            ans.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
    else:
        if dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
print(*map(chr, ans), sep='')

Measured memory_bytes: 115292
N=int(input())
T_N=input().split()
list_time = []
for i in range(N):
    list_time.append(int(T_N[i]))
#Ti秒の総和を求める
sum=sum(list_time)
M=int(input())
for i in range(M):
    p,x=map(int,input().split())
#ドリンク飲んだ時と飲まないときの差を元の合計に足す。
    ans=sum+x-list_time[p-1]
    print(ans)
    


Measured memory_bytes: 2940
n,m,c = map(int, input().split())
b = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for i in range(n):
    sm = 0
    for j in range(m):
        sm += a[i][j]*b[j]
    if(sm + c > 0):
        ans += 1
print(ans)

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

#define int long long
#define ll long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<(int)n ; i++)
#define rf(i,n,a) for(int i=n ; i>=a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
#define fill(a,v) memset(a,v,sizeof(a))
#define d1(a) cout << a << "\n"
#define d2(a,b) cout << a << " " << b << "\n"
#define d3(a,b,c) cout << a << " " << b << " " << c << "\n"
#define d4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << "\n"
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);

typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;

int32_t main(){
	fast;
	int x,y,z;
	cin >> x >> y >> z;
	d3(z,x,y);
}


Measured memory_bytes: 256
import sys

n = int(input())
a = list(map(int, input().split()))
 
ans = 1
r,g,b = 0,0,0
 
for x in a:
    ans *= [r,g,b].count(x)

    if r == x:r+=1
    elif g == x:g +=1
    elif b == x:b +=1
    else:
        print(0)
        sys.exit()
ans %= 1000000007 
print(ans)


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

import sys

def main():
    input = sys.stdin.readline
    l,r,d = map(int, input().split())
    l_count = l // d
    r_count = r // d
    result = 0
    if l % d == 0:
        print(r_count - l_count + 1)
    else:
        print(r_count - l_count)

    return


if __name__ == '__main__':
    main()

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

#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

signed main(){
	int x, y;
	cin >> x >> y;
	cout << (abs(x-y) <= 1 ? "Brown" : "Alice") << endl;
	return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define watch(x) cout << (#x) << " is " << (x) << '\n'
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pi;
typedef double db;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; }
//head


bool is_palindrome(string s){
    int n = s.size();
    for (int i = 0; i < n/2; i++){
        if (s[i] != s[n-i-1]) return false;
    }
    return true;
}

void solve(){
    ll l;
    cin >> l;
    db a = (db) l / 3;
    db ans = a*a*a;
    cout << setprecision(20) << ans << '\n';
}

int main(void){ 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    //int t; cin >> t; while (t--)
        solve();
}


Measured memory_bytes: 3784
#include<iostream>
using namespace std;
int a[6];
int main()
{
	int i, min = 9, f, c = 1, s = 0;
	for(i = 1; i <= 5; i ++)
	{
		cin >> a[i];
	}
	for(i = 1; i <= 5; i ++)
	{
	    f = a[i] % 10;
		if(f != 0 && f < min)
		{
		   min = f;
		   c = i;
	    }
	}
	for(i = 1; i <= 5; i ++)
	{
		if(i != c)
		{
			s = s + (a[i] + 9) / 10 * 10;
	    } 
	}
	cout << s + a[c];
	return 0;
}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
#define MN 2005
#define inf 1e15
long long n,x,a[MN*2],f[MN][MN*2];
long long ans=inf;
int main(){
	n=read(),x=read();register int i,j,k;
	memset(f,0x3f,sizeof f);
	for(i=1;i<=n;i++) a[i]=a[i+n]=f[0][i]=f[0][i+n]=read();
    for(i=n+1;i<=n+n;i++)for(j=1;j<n;j++) f[j][i]=min(f[j-1][i],a[i-j]);
    for(k=0;k<n;k++){
        long long res=0;
        for(i=n+1;i<=n+n;i++) res+=f[k][i];
        ans=min(ans,res+k*x);
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 63104
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		System.out.println(Math.max(c - (a - b), 0));
		sc.close();
	}
}

Measured memory_bytes: 22356
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    int ans{1};
    if(s=="SSS") ans=0;
    else if(s=="RRR") ans=3;
    else if(s=="RRS" or s=="SRR") ans=2;
    cout<<ans<<'\n';
}

Measured memory_bytes: 3616
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.xise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

ll N,M,H,W,K,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
//const ll INF = 1LL << 60;
//typedef pair<ll,ll> P;
typedef pair<int, int> P;
bool chmx(int &a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

bool chmn(int &a, int b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

int d[9];

int main(){
    d[0]=1;
    d[1]=1;
    reps(i,2,9){
        d[i]=d[i-1]*i;
    }
    int n;
    cin >> n;
    int P=0,Q=0;
    int p[n],q[n];
    rep(i,n){
        cin >> p[i];
    }
    rep(i,n){
        cin >> q[i];
    }
   
    
    vector<int> v(n);
    iota(v.begin(), v.end(), 1);       // v に 1, 2, ... N を設定
    int k=0;
    do {
        //for(auto x : v) //cout << x << " "; cout << "\n";    // v の要素を表示
        k++;
        bool pp=1,qq=1;
        rep(i,n){
            if(v[i]!=p[i]){
                pp=0;
            }
            if(v[i]!=q[i]){
                qq=0;
            }
        }
        if(pp){
            P=k;
        }
        if(qq){
            Q=k;
        }
    } while( next_permutation(v.begin(), v.end()) );     // 次の順列を生成
    
    
    cerr<<P<<' '<<Q<<endl;
    int ans=abs(P-Q);
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int sm,mon;
  while(1){
    cin >> sm;
    if(sm==0)break;
    for(int i=0;i<9;i++){
      cin >> mon;
      sm-=mon;
    }
    cout << sm << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <bits/stdc++.h>
#include <string>

using namespace std;
int main()
{
    unsigned long long count,i,sum = 0LL;

    cin >> count;


    for(i = 1;i<=count;i++){
        if(i % 3 != 0 && i % 5 != 0) {
            sum += i;
        }
    }

    cout<<sum<<endl;



    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=2e5+1;
const ll INF=4e18;
void solve()
{
	ll A,B;
	cin>>A>>B;
	for(ll i=1;i<=3;i++)
	{
		if(i!=A&&i!=B)
		{
			cout<<i<<"\n";
			break;
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll T=1,p=0;
	//cin>>T;
	do
	{
		solve();
		p++;
	}while(p<T);
	return 0;
}



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

bool is_leap(int y) {
  if(y % 400 == 0) {
    return true;
  }else if(y % 100 == 0) {
    return false;
  }else if(y % 4 == 0) {
    return true;
  }

  return false;
}

int main() {
  int a, b;
  int cnt = 0;
  while(cin >> a >> b ) {
    if(a == 0 && b == 0) {
      break;
    }
    if(cnt) {
      cout << endl;
    }
    cnt++;

    bool flg = false;
    for(int i = a; i <= b; i++) {
      if(is_leap(i)) {
        cout << i << endl;

        flg = true;
      }
    }
    if(!flg) {
      cout << "NA" << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 2996
import java.util.Scanner;//导入Scanner模块，用于输入
public class Main {
    public static void main(String[] args)  {
        Scanner scan=new Scanner(System.in);//这样可以方便输入
        int a=scan.nextInt(),c=scan.nextInt();//输入a,c
        int b=(c<<1)-a;//由我们得到的关系式直接计算答案
        System.out.println(b);//输出b，一定要换行
    }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
 using namespace std;
int main()
 {
int n;
cin>>n;
string ar[n];
map<string,int> mp;
for(int i=0;i<n;i++)
 {
cin>>ar[i];
}
int maxi=0;
for(int i=0;i<n;i++)
 {
if(mp.find(ar[i])!=mp.end())
mp[ar[i]]++;
else mp[ar[i]]=1;
maxi=max(maxi,mp[ar[i]]);
}
vector<string> vec;
for(auto i: mp)
  {
  if(i.second == maxi)
   vec.push_back(i.first);
 }
sort(vec.begin(),vec.end());
 for(int i=0;i<vec.size();i++)
  cout<<vec[i]<<endl;
 return 0;
}


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

using namespace std;

int main() {
  int d,t;
  double s;
  cin >> d >> t >> s;
  
  if (d/s <= t) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }
  
  return 0;

} 

Measured memory_bytes: 3672
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
vector<vector<ll int>> graph;
vector<bool> visited;
vector<vector<ll int>> dp;
ll int MOD = 1e9 + 7;

void dfs(ll int u){
	visited[u] = true;
	for(auto i = graph[u].begin();i!=graph[u].end();i++){
		if(visited[*i]==false){
			dfs(*i);
			dp[u][0] = (dp[u][0] * (dp[*i][0]+dp[*i][1]))%MOD;
			dp[u][1] = (dp[u][1] * dp[*i][0])%MOD;		
		}
	}
}

int main(int argc, char const *argv[])
{
	ll int n;
	cin>>n;
	visited.assign(n,false);
	graph.assign(n,vector<ll int>());
	dp.assign(n,vector<ll int>(2,1));
	for(ll int i=0;i<(n-1);i++){
		ll int x,y;
		cin>>x>>y;
		graph[x-1].push_back(y-1);
		graph[y-1].push_back(x-1);
	}
	dfs(0);
	cout<<(dp[0][0]+dp[0][1])%MOD;
	return 0;
}

Measured memory_bytes: 13952
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
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; }
//get the biggest element.
template<typename KeyType, typename ValueType>
std::pair<KeyType,ValueType> get_max( const std::map<KeyType,ValueType>& x ) {
  using pairtype=std::pair<KeyType,ValueType>;
  return *std::max_element(x.begin(), x.end(), [] (const pairtype & p1, const pairtype & p2) {
        return p1.second < p2.second;
  });
}
using namespace std;
using P = pair<int,int>;
using ll = long long;
const ll INF = 1LL<<60;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i , n) cin >> a[i];
  ll min = a[0];
  ll ans = n;
  rep(i, n) {
    if (a[i] <= min) {
      min = a[i];
    } else {
      --ans;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4000
#include<iostream>
using namespace std;
#define int long long int
int32_t main()
{
     int R,G,B,n;
     cin>>R>>G>>B>>n;
     int answer=0;
     int j;
     for(int i=0;i<=n/R;i++)
     {
		 for(j=0;j<=(n-i*R)/G;j++)
		 {
			 int x=n-i*R-j*G;
			 if(x>=0&&x%B==0)
			    answer++;
		 }
	 }
	 cout<<answer<<endl;
}


Measured memory_bytes: 256
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    int n;
    R(n);
    vector<pair<string,PII>>d;
    FOR(i,1,n){
        string s;
        int v;
        R(s,v);
        d.PB(MP(s,MP(-v,i)));
    }
    sort(ALL(d));
    REP(i,n){
        W(d[i].S.S);
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define pb push_back
#define sfor(j,a) for(int i(j); i < a; ++i)

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int N,A,B; cin >> N >> A >> B;
    cout << min(A,B) << " " << max(0,(A+B)-N);
    return 0;
}


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

int main(){
    while(1){
        int a, b, value;
        char op;
        scanf("%d %c %d", &a, &op, &b);
        switch(op){
        case '+':
            value = a + b;
            break;
        case '-':
            value = a - b;
            break;
        case '*':
            value = a * b;
            break;
        case '/':
             value = a / b;
             break;
        case '?':
             return 0;
        }
        printf("%d\n", value);
    } 
    return 0;
}

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

n = int(raw_input())
ans = []
for i in range(n):
    a = str(raw_input())
    b = str(raw_input())
    if len(a) < len(b):
        a, b = b, a
    l = len(a)
    for j in range(len(b), len(a)):
        b = '0'+b
    sum = ""
    nextdigit = 0
    for j in range(l):
        digit = int(a[l-1-j]) + int(b[l-1-j]) + nextdigit
        nextdigit = 0
        if (nextdigit+digit) >= 10:
            nextdigit = 1
            digit %= 10
        sum = str(digit) + sum
    if nextdigit:
        sum = '1'+sum
    ans.append(sum)
for i in ans:
    print i if len(i) <= 80 else "overflow"

Measured memory_bytes: 6324
N, Q = map(int, input().split())

# ab = [list(map(int, input().split())) for _ in range(N - 1)]
# px = [list(map(int, input().split())) for _ in range(Q)]

# graph = [[] for _ in range(N)]
# for i, (ai, bi) in enumerate(ab):
#     graph[ai - 1].append(bi - 1)
#     graph[bi - 1].append(ai - 1)

from collections import deque
    
# c = [0] * N
# for j, (pj, xj) in enumerate(px):
#     c[pj - 1] += xj

graph = [[] for _ in range(N)]
for _ in range(N - 1):
    ai, bi = map(int, input().split())
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)
    
c = [0] * N
for _ in range(Q):
    pj, xj = map(int, input().split())
    c[pj - 1] += xj
    
ans = [None] * N
q_0 = deque([(0, 0)])
while len(q_0) > 0:
    score, src = q_0.popleft()
    # print("#", score, src)
    score_tmp = score + c[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] == None:
            q_0.append((score_tmp, dst))

print(' '.join(map(str, ans)))

Measured memory_bytes: 135160
import sys
sys.setrecursionlimit(10**6)

N,M=map(int,input().split())
G = [[] for i in range(N)]
A = []
B = []

for i in range(M):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
    A.append(a)
    B.append(b)


def dfs(x):
    global old
    old[x] = True
    for i in G[x]:
        if not(old[i]):
            dfs(i)

ans = 0
for i in range(M):
    a,b = A[i], B[i]
    G[a].remove(b)
    G[b].remove(a)

    old = [False]*N
    dfs(0)
    if old != [True]*N:
        ans += 1

    G[a].append(b)
    G[b].append(a)

print(ans)


Measured memory_bytes: 3064
# Segment Tree
class Segment:
    def __init__(self, N, init_val):
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.dat = [identity_element]*(2*self.N0)
        # 値を代入
        for i in range(N):
            self.dat[i+self.N0-1]=init_val[i]    
        # 構築
        for i in range(self.N0-2,-1,-1) :
            self.dat[i]=segfunc(self.dat[2*i+1],self.dat[2*i+2]) 

    # k番目の要素の値をxに変更
    def update(self, k, x):
        k += self.N0-1
        self.dat[k] = x
        while k >= 0:
            k = (k-1)//2
            self.dat[k] = segfunc(self.dat[2*k+1], self.dat[2*k+2])

    # 区間[l, r)のsegfuncを求める
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = identity_element
        # 区間を列挙しながらsegfuncを求める
        while L < R:
            if R & 1:
                R -= 1
                s = segfunc(s, self.dat[R-1])
            if L & 1:
                s = segfunc(s, self.dat[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

# segfunc : min, +, *, xor, gcd
# identity_element : 単位元(min:inf, 和:0, 積:1, xor:0, gcd:0)

from fractions import gcd
def segfunc(x,y):
    return gcd(x,y) # 変える
identity_element = 0 # 変える

n = int(input())
a = list(map(int,input().split()))

h = Segment(n, a)
ans = 0
for i in range(n):
    ans=max(ans,gcd(h.query(0,i), h.query(i+1,n)))
print(ans)


Measured memory_bytes: 90464
import bisect as bs
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        s = L[i] + L[j]
        ans += bs.bisect_left(L,s) - j - 1
        # bisect.bisect_left(list, x)
        # はリストにxを挿入できる点を返す
        # すなわち、
        # (val < x for val in list[0:i]) + (val >= x for val in list[i:len(list)])
print(ans)

Measured memory_bytes: 3188
# 27
n,x = map(int, input().split())
aa = list(map(int, input().split()))
aa.sort()
ans = 0
for a in aa:
    if x<a:
        break
    ans+=1
    x-=a
else:    #for else文 - breakすると入らないことを利用=ループ完遂した場合の終端処理
    if x>0:
        ans-=1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    double a;
    if (N % 2 == 1){
        a = N / 2 + 1;

    }
    else{
        a = N / 2;
    }

    double b = a / N;
	//cout << a << N << endl;
  
    cout << b << setprecision(10) << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(n - 1);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n - 1; i++) cin >> c[i];
    long long ans = 0;
    for (int i = 0; i < n; i++){
        ans += b[a[i] - 1];
        if (i != n - 1){
            if (a[i + 1] == a[i] + 1) ans += c[a[i] - 1];
        }
    }
    cout << ans << endl;
}

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

struct Unionfind
{
    int parent[10005];

    Unionfind()
    {
        fill_n(parent, 10005, -1);
    }

    int getp(int x)
    {
        if(parent[x] == -1) return (x);
        return (parent[x] = getp(parent[x]));
    }

    void unite(int a, int b)
    {
        a = getp(a), b = getp(b);
        if(a != b) parent[a] = b;
    }

    int same(int a, int b)
    {
        if(getp(a) == getp(b)) return (1);
        return (0);
    }
};

int main()
{
    int N, Q;
    Unionfind tree;

    cin >> N >> Q;

    while(Q--) {
        int A, B, C;
        cin >> A >> B >> C;
        if(A == 0) tree.unite(B, C);
        else cout << tree.same(B, C) << endl;
    }

    return (0);
}

Measured memory_bytes: 3196
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
ll n, m;
vector<vector<ll>> c;
int main(void){
    cin >> n >> m;
    c.resize(n);

    for(int i = 0; i < n; i++){
        ll x, y, z;
        cin >> x >> y >> z;
        c[i].push_back(x);
        c[i].push_back(y);
        c[i].push_back(z);
    }

 
    ll ans = 0;
    for(int bit = 0; bit < (1 << 3); bit++){
        vector<ll> pattern;
        for(int i = 0; i < 3; i++){
            if(bit & (1 << i)){
                pattern.push_back(i);
            }
        }
        vector<vector<ll>> copyc = c;
        vector<ll> tmp(n);
        for(int i = 0; i < n; i++){
            ll t = 0;
            for(int j = 0; j < pattern.size(); j++){
                copyc[i][pattern[j]] *= -1;
            }
            for(int j = 0; j < 3; j++){
                t += copyc[i][j];
            }
            tmp[i] = t;
        }

        sort(tmp.begin(), tmp.end(), greater<ll>());
        ll tmpans = 0;
        for(int i = 0; i < m; i++){
            tmpans += tmp[i];
        }

        ans = max(ans, tmpans);
        
    }
    cout << ans << endl;

}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<iomanip>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
int main(){
  int a, b, c;
  cin >> a >> b >> c;
  if(c > a - b){
  cout << c - a + b << "\n";
  }
  else{
    cout << "0\n";
  }
}


Measured memory_bytes: 3612
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;


int main()
{ios_base::sync_with_stdio(false);
ll n,a[205],ans=1e18+7;
cin>>n;
rep(i,0,n-1)cin>>a[i];

rep(i,-100,100)
{
	ll s=0;
	rep(j,0,n-1)
	{
		s+=(i-a[j])*(i-a[j]);
	}
	ans=min(ans,s);
}
ol(ans);
return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <iostream>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
 
#ifndef ONLINE_JUDGE
	#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#else
	#define DEBUG(x) do {} while(0);
#endif
 
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
#define PER(i, N) for(int (i) = (N)-1; (i) >= 0; (i)--)
#define REP(i, N) for(int (i) = 0; (i) < (int)(N); (i)++)
 #include <iomanip>
using namespace std;
typedef long long ll;
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }


void solve(istream& cin, ostream& cout) {
	ll A,B,N;
	cin >>A>>B>>N;
	cout << (min(N, B-1)*A)/B <<endl;
}


int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	solve(cin, cout);
	/*
	{
		istringstream instr("2\n2\n14");
		solve(instr, cout);
	}
 */
	return 0;
}


Measured memory_bytes: 3160