akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

///******************************** C o n t a i n e r ********************************///

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;

///*********************************** C o n s t ***********************************///

const int       N=1e6+3;
const double    PI = acos(-1);
const ll        MOD=1000000007;                 ///1e9+7
ll dx[] = {+1, 0, -1, 0, +1, +1, -1, -1};
ll dy[] = {0, +1, 0, -1, +1, -1, +1, -1};

///********************************** M a r c o ***********************************///

#define pb push_back
#define F first
#define S second
#define test int tc; cin>>tc; while(tc--)
#define forn(i,n) for(i=0;i<n;i++)
#define rforn(i,n) for(i=n-1;i>=0;i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) x.size()
#define el <<'\n'
#define sp <<' '
#define print(a) {for(auto x:a)cout<<x<<" ";cout<<endl;}
#define mem(a,b) memset(a, b, sizeof(a))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define sqr(a) (a)*(a)

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

///*********************************** F u n c t i o n ***********************************///

ll powmod(ll a,ll b){ll p=MOD;a%=p;if(!a) return 0;ll pr=1;while(b>0){if(b&1){pr*=a;pr%=p;--b;}a*=a;a%=p;b/=2;}return pr;}
bool isPrime(ll n){ if(n<=1)return false;if(n<=3)return true;if(n%2==0 or n%3==0)return false;for(ll i=5;i*i<=n;i+=6){if(n%i==0 or n%(i+2)==0)return false;}return true;}
void seive(bool a[]){ll mx=sqrt(N),ii,jj;for(ii=3;ii<=mx;ii+=2)if(!a[ii])for(jj=ii*ii;jj<=N;jj+=2*ii)a[jj]=true;}
void numofdiv(ll a[]){ll mx=sqrt(N),ii,jj;for(ii=1;ii<=mx;ii++){for(jj=ii*ii;jj<=N;jj+=ii){if(jj==ii*ii) a[jj]++; else a[jj]+=2;}}}
void sumofdiv(ll a[]){ll mx=sqrt(N),ii,jj;for(ii=1;ii<=mx;ii++){for(jj=ii*ii;jj<=N;jj+=ii){if(jj==ii*ii) a[jj]+=ii; else a[jj]+=ii+jj/ii;}}}

///**************************************************** C o d e ****************************************************///
///-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=///



void _case()
{
    ll n,i;
    cin>>n;
    ll a[n],b[n];
    forn(i,n) cin>>a[i],b[i]=a[i];
    if(n==1){cout<<0 el; return;}
    sort(b,b+n);
    for(i=0;i<n;i++){
        if(a[i]==b[n-1]) cout<<b[n-2] el;
        else cout<<b[n-1] el;
    }
}

main()
{
//      fastio();
        _case();

}


///Thank you.


///Brainless_Loco Terminates Here!


Measured memory_bytes: 6720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;
int N;

signed main()
{
    cin >> N;
    vector<int> a(N);
    rep(i, N) { cin >> a[i]; }
    int cnt = 1;
    rep(i, N)
    {
        if (cnt == a[i]) {
            cnt++;
        }
    }
    if (cnt != 1) {
        cout << N - cnt + 1 << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

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

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    a = list(map(int, input().split()))

    return N, a


def main(N: int, a: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 正整数の数(2 <= N <= 3000)
        a (list): 正整数(2 <= a_i <= 10^5)
    """
    # 求解処理
    ans = sum(a) - N

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, a = get_input()

    # メイン処理
    main(N, a)


Measured memory_bytes: 9248
#include <stdio.h>
    int main(void){
    int n,x,a,b,c,i;
    while(1){
        scanf("%d %d",&n,&x);
        i=0;
        if(n==0 && x==0) break;
        for(a=1;a<=n;a++){
            for(b=a+1;b<=n;b++){
                for(c=b+1;c<=n;c++){
                    if((a+b+c)==x) i++;
                    
                }
            }
        }
    printf("%d\n",i);    
    }  
    return 0;
}


Measured memory_bytes: 2040
#include <iostream>
#include <vector>

using namespace std;

using Graph = vector<vector<bool>>;

bool GoodPath(const vector<int> &path, const Graph &g)
{
    for (size_t i = 1; i < path.size(); i += 1) {
        auto prev = path[i - 1];
        auto curr = path[i];

        if (!g[prev][curr]) {
            return false;
        }
    }
    return true;
}

int Back(vector<int> &st, vector<bool> &used, int level, const Graph &g)
{
    if (level >= (int)g.size()) {
        return GoodPath(st, g) ? 1 : 0;
    }

    auto total = 0;
    for (size_t i = 0; i < g.size(); i += 1) {
        if (used[i]) {
            continue;
        }

        st[level] = i;
        used[i] = true;

        total += Back(st, used, level + 1, g);
        used[i] = false;
    }
    return total;
}

int CountPaths(const Graph &g)
{
    vector<int> st(g.size());
    vector<bool> used(g.size(), false);

    st[0] = 0;
    used[0] = true;

    return Back(st, used, 1, g);
}

int main()
{
    int nodes, edges;
    cin >> nodes >> edges;

    Graph graph(nodes, vector<bool>(nodes, false));
    for (auto i = 0; i < edges; i += 1) {
        int a, b;
        cin >> a >> b;
        graph[a - 1][b - 1] = graph[b - 1][a - 1] = true;
    }

    auto res = CountPaths(graph);
    cout << res << "\n";

    return 0;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
a=[0]*M
b=[0]*M
r=[0]*N
for i in range(M):
  a[i],b[i]=map(int,input().split())
  #print(a[i]-1,b[i]-1)
  r[a[i]-1] +=1
  r[b[i]-1] +=1
  
for item in r:
  print(item)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MOD = 1e9 + 7;

template <class T>
T ArithmeticSeries(T a, T d, T n) {
  return n * (2 * a + (n - 1) * d) / 2;
}

int main() {
  ll n, k;
  cin >> n >> k;

  ll r = 0;
  for (ll i = k; i <= n + 1; i++) {
    ll s_min = ArithmeticSeries(0ll, 1ll, i);
    ll s_max = ArithmeticSeries(n, -1ll, i);
    r += s_max - s_min + 1;
    r %= MOD;
  }
  cout << r << endl;
}


Measured memory_bytes: 3552
import java.util.*;
import java.util.stream.Collectors;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String S=scanner.next();
        int w=scanner.nextInt();
        for(int i=0;i<S.length();i++){
            if(i%w==0){
                System.out.print(S.charAt(i));
            }
        }
        System.out.println();
    }
}

Measured memory_bytes: 23252
#include <iostream>
#include <string>
using namespace std;
int main()
{
  string N;
  cin >> N;
  int sum = 0;
  for (unsigned int i = 0; i < N.length(); i++) {
    sum += (int)(N[i] - '0');
  }
  if (sum%9==0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3696
#include<stdio.h>
int main(){
  int n,c;
  while(1){
    scanf("%d",&n);
    if(n==0)break;
    for(c=0;n!=1;c++){
      if(n%2==0){
	n/=2;
      }
      else{
	n=n*3+1;
      }
    }
    printf("%d\n",c);
  }
  return 0;
}

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

int main(){
    string s;
    cin >> s;
    int ans=100000;
    bool flag=false;
    for(char i = 'a' ;i <= 'z'; i++){
        flag=false;
        for(int j=0;j<s.length();j++){
            if (i==s[j]){
                flag=true;
                break;
            }
        }
        if (!flag){
            cout << i <<endl;
            break;
        }
    }
    if (flag){
        cout << "None" <<endl;
    }
    return 0;
}

Measured memory_bytes: 512
s = input()
lens = len(s)
t = input()
lent = len(t)
ss = set()
for i in range(lens - lent + 1):
    ss.add(s[i:i+len(t)])
ans = float('inf')

for text in ss:
    tmp = 0
    for i in range(lent):
        if text[i] != t[i]:
            tmp += 1
    ans = min(ans,tmp)

print(ans)

Measured memory_bytes: 9136
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <map>
#include <string>
#include <math.h>
#include <vector>
#include <cstdlib>
#include <queue>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

using namespace std;

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

    if (moji[0] == moji[1] && moji[0] == moji[2])
    {
        cout << "Yes" << endl;
    }
    else if (moji[1] == moji[2] && moji[1] == moji[3])
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main() {
	string s;cin>>s;
	auto posc = s.find("C");
	auto posf = s.rfind("F");
  if(posc != string::npos &&posf !=string::npos){
    if(posc<posf){
      cout << "Yes" << endl;	
    } else {
      cout << "No" << endl;
    }
  } else {
    cout << "No" << endl;
  }
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

destoryed_monsters = 0
for n in range(N):
    c1 = min(A[n], B[n])
    c2 = min(A[n+1], max(0, B[n]-A[n]))
    A[n+1] -= c2
    destoryed_monsters += (c1+c2)
print(destoryed_monsters)

Measured memory_bytes: 18476
INF = 1000000000+7

x,y = map(int, input().split())
a = 2*x-y
b = -x + 2*y
if a%3!=0 or b%3!=0:
    print(0)
    exit()

n = a//3
m = b//3
nm = n+m

def cmb(n,r):
    if r > n:
        return 0
    if n - r < r:
         r = n - r
    if r > n:
        return 0
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

if n<0 or m<0:
    print(0)
    exit()
ans = cmb(nm,n)
print(ans%INF)


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

int main() {
	int N, W;
	cin >> N >> W;
	vector<int> w(N), v(N);
	for (int i = 0; i < N; i++) cin >> w[i] >> v[i];

	vector<vector<vector<int>>> dp(N+1,
		vector<vector<int>>(N+1,
			vector<int>(3*N+1)));
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k <= 3*N; k++) {
				int k_prev = k - w[i-1] + w[0];
				if (k_prev < 0 || k_prev > 3*N) {
					dp[i][j][k] = dp[i-1][j][k];
				}
				else {
					dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k_prev] + v[i-1]);
				}
			}
		}
	}

	int a = min(N, W/w[0]);
	int b = min(3*N, W-w[0]*a);
	int ans = 0;
	while(a >= 0 && b <= 3*N) {
		ans = max(ans, dp[N][a][b]);
		a--;
		b = W-w[0]*a;
	}
	cout << ans << endl;	
}


Measured memory_bytes: 12672
N = int(input())
s1 = input()
s2 = input()
ans = 1
being_horizontal = False
was_horizontal = False
was_vertical = False
MOD = 10**9+7
for i in range(N):

    if not was_horizontal and not being_horizontal and not was_vertical: # 開始時
        if s1[i] != s2[i]:
            ans *= 6
            being_horizontal = True
        else:
            ans *= 3
            was_vertical = True
    elif being_horizontal:
        being_horizontal = False
        was_horizontal = True
    elif was_horizontal and s1[i] == s2[i]:
        was_horizontal = False
        was_vertical = True
    elif was_horizontal and s1[i] != s2[i]:
        ans *= 3
        being_horizontal = True
        was_horizontal = False
    elif was_vertical and s1[i] == s2[i]:
        ans *= 2
        was_vertical = True
    elif was_vertical and s1[i] != s2[i]:
        ans *= 2
        was_vertical = False
        being_horizontal = True
    ans %= MOD
print(ans)

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

int main() {
    int N ;
    long long D ;
    
    cin >> N >> D ;
    
    vector< vector<int> > XY( N , vector<int>(2) ) ;
    
    for( int i=0 ; i<N ; i++){
        for( int j=0 ; j<2 ; j++){
            cin >> XY.at(i).at(j) ;
        }
    }
    
    vector<long long> d(N) ;
    for( int i=0 ; i<N ; i++){
        d.at(i) = pow( XY.at(i).at(0),2) + pow( XY.at(i).at(1),2) ;
    }
    
    int ans=0 ;
    long long dd = D*D ;
    
    for( int i=0 ; i<N ; i++){
        if( d.at(i) <= dd ){
            ans++ ;
        }
    }
    cout << ans << endl;
}



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

int main() {
    int a, b;
    char op['5'];

    scanf("%i %s %i", &a, op, &b);

    if (strcmp(op, "+") == 0) {
        printf("%d", a + b);
    } else if (strcmp(op, "-") == 0) {
        printf("%d", a - b);
    }

    return 0;
}

Measured memory_bytes: 128
n = int(input())
h = list( map(int,input().split()) )
x = [0] * (n+1)

c = h[0]
for i in range(1,n):
  if h[i] <= c:
    x[i] = 1
  c = h[i]

ans = 0
tmp = 0
for i in x:
  if i == 1:
    tmp += 1
  else:
    ans = max(ans,tmp)
    tmp = 0

print(ans)

Measured memory_bytes: 14252
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
d = Counter(a)
c = [0 for _ in range(max(a))]
for k, v in d.items():
    c[k - 1] = v * (v - 1) / 2

ans = sum(c)
for i in range(n):
    p = a[i]
    res = c[p - 1] * (d[p] - 2) / d[p]
    ans -= c[p - 1] - res
    print(int(ans))
    ans += c[p - 1] - res


Measured memory_bytes: 26908
#include <stdio.h>
int main(void){
int a,b,c;
  scanf("%d %d %d",&a,&b,&c);
  if((a==5&&b==5&&c==7)||(a==5&&b==7&&c==5)||(a==7&&b==5&&c==5)){printf("YES");}
  else{printf("NO");}
return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1LL << 30 -1;
int MOD = 1e9+7;
main(){
    int N,M;
    cin >> N >> M;
    int dist[N][N];
    int V[M][3];
    for(int i = 0;i < N;i++)for(int j = 0;j < N;j++){
        dist[i][j] = INF;
    }
    for(int i = 0;i < M;i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--,b--;
        dist[a][b] = dist[b][a] = c;
        V[i][0] = a;
        V[i][1] = b;
        V[i][2] = c;
    }
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            for(int k = 0;k < N;k++){
                dist[j][k] = min(dist[j][k],dist[j][i]+dist[i][k]);
            }
        }
    }
    int cnt = 0;
    for(int i = 0;i < M;i++){
        cnt += (dist[ V[i][0] ][ V[i][1] ] != V[i][2]);
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <functional>
#include <cctype>
#include <climits> // INT_MAX ...
#include <cstring> // 

using namespace std;

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

    int n;
    cin >> n;
    map<int, int> mp;
    bool f = false;
    while (n--) {
        int x;
        cin >> x;
        if (mp.count(x)) f = true;
        else mp[x]++;
    }
    if (f) cout << "NO" << endl;
    else cout << "YES" << endl;

	return 0;
}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
int n;
int minn=0x3f3f3f3f;
int main()
{
	cin>>n;
	for(int i=1;i<=n/2;i++)
	{
		int a=n-i,b=i;
		int temp=0;
		while(a)
		{
			temp+=a%10;
			a/=10;
		}
		while(b)
		{
			temp+=b%10;
			b/=10;
		}
		minn=min(temp,minn);
	}
	cout<<minn<<endl;
	return 0;	
}

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

using namespace std;

bool dfs(queue<int> a, stack<int> b, stack<int> c)
{
	if (a.empty()) return true;

	bool f1 = false, f2 = false;

	int item = a.front(); a.pop();

	if (b.top() < item) {
		b.push(item);
		f1 = dfs(a, b, c);
		b.pop();
	}

	if (c.top() < item) {
		c.push(item);
		f2 = dfs(a, b, c);
		c.pop();
	}

	return f1 || f2;
}

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

	while (n--) {
		queue<int> a;
		stack<int> b, c;

		b.push(0);
		c.push(0);

		for (int i = 0; i < 10; ++i) { int v; cin >> v; a.push(v); }

		cout << (dfs(a, b, c) ? "YES" : "NO") << endl;
	}
}

Measured memory_bytes: 1216
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;

string S,T;

bool chk(char a,char b){
    if(a==b || a=='?' || b=='?') return true;
    return false;
}

int main(){
    cin>>S>>T;

    if(S.size()<T.size()){
        cout<<"UNRESTORABLE"<<endl;
        return 0;
    }
    int begin=-1;
    rep(i,S.size()-T.size()+1){
        bool flag=true;
        rep(j,T.size()){
            if(!chk(S[i+j],T[j])){
                flag&=false;
            }
        }
        if(flag) begin=i;
    }
    if(begin==-1){
        cout<<"UNRESTORABLE"<<endl;
        return 0;
    }

    rep(i,S.size()){
        if(S[i]=='?') S[i]='a';
    }
    for(int i=begin;i<begin+T.size();i++){
        S[i]=T[i-begin];
    }

    cout<<S<<endl;
}

Measured memory_bytes: 256
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

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

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1000*1007;
const ll inf=1e18;

int n;
ll m;

ll tab[nax];

ll lew[nax];
ll pra[nax];

ll wyn=inf;

int ok[nax];

void oznacz(int a, int b)
{
	ok[a]++;
	ok[b]--;
}

int check(ll v)
{
	for (int i=0; i<4*n; i++)
		ok[i]=0;
	for (int i=0; i<n; i++)
	{
		ll x=(m-lew[i])%m;
		int l=lower_bound(pra, pra+2*n, x)-pra;
		int p=upper_bound(pra, pra+2*n, x+v)-pra;
		//~ debug() << lew[i] << "   " << l << " " << p;
		if (l>=p)
			return 0;
		oznacz(l+i, p+i);
	}
	for (int i=0; i<4*n; i++)
		ok[i+1]+=ok[i];
	for (int i=0; i<n; i++)
		if (ok[i]+ok[i+n]+ok[i+2*n]+ok[i+3*n]==n)
			return 1;
	return 0;
}

int main()
{
	scanf("%d%lld", &n, &m);
	for (int i=0; i<2*n; i++)
		scanf("%lld", &tab[i]);
	sort(tab, tab+2*n);
	
	for (int i=0; i<2*n; i++)
	{
		lew[i]=tab[2*i];
		pra[i]=tab[2*i+1];
	}
	for (int i=0; i<n; i++)
		pra[i+n]=pra[i]+m;
	//~ debug() << range(pra, pra+2*n);
	//~ debug() << check(5);
	ll bsa=0;
	ll bsb=m-1;
	while(bsa<bsb)
	{
		ll bss=(bsa+bsb)>>1;
		if (check(bss))
			bsb=bss;
		else
			bsa=bss+1;
	}
	printf("%lld\n", bsa);
	return 0;
}


Measured memory_bytes: 14208
def ary2(x, y, v): return [[v for _  in range(y)] for _ in range(x)]

n, a = map(int, input().split())
x = list(map(int, input().split()))
m = max(x)
dp = ary2(n + 1, n + 1, False)#(選べる枚数（範囲）0 ~ n, 選んだ枚数0 ~ n = 合計0 ~ n * max(x) : パターン数 の辞書

for i in range(n + 1):
    for j in range(n + 1):
        if j == 0:
            dp[i][j] = {0:1}
        else:
            dp[i][j] = dict()

for i in range(1, n + 1):
    for j in range(1, i + 1):
        for s in dp[i - 1][j - 1].keys():
            dp[i][j][s + x[i - 1]] = dp[i][j].get(s + x[i - 1], 0) + dp[i - 1][j - 1].get(s, 0)
        for s in dp[i - 1][j].keys():
            dp[i][j][s] = dp[i][j].get(s, 0) + dp[i - 1][j].get(s, 0)

ans = 0
for j in range(1, n + 1):
    ans += dp[n][j].get(j * a, 0)

print(ans)

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x;
  cin >> x;
  if (x < 1200)
    cout << "ABC" << '\n';
  else
    cout << "ARC" << '\n';
  return 0;
}


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

using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
#define N 120000
#define INF 0x3f3f3f3f
#define P(x,y) make_pair(x,y)

LL n,ans,mn,sz[N];
vector<pii> g[N];

void dfs(LL u,LL fa){
	sz[u]=1;
	LL t=0;
	for (auto i:g[u]){
		LL v=i.first;
		if (v==fa) continue;
		dfs(v,u);
		sz[u]+=sz[v];
		t=max(t,sz[v]);
		ans+=i.second*min(sz[v],n-sz[v])*2;
	}
	t=max(t,n-sz[u]);
	if (t<(n+1)/2){
		mn=INF;
		for (auto i:g[u]) mn=min(mn,i.second);
	}
	if (n%2==0&&t==n/2){
		for (auto i:g[u]){
			LL v=i.first;
			if (v!=fa&&sz[v]==n/2) mn=i.second;
		}
	}
}

int main(){
	scanf("%lld",&n);
	for (LL i=1;i<n;++i){
		LL x,y,z; scanf("%lld%lld%lld",&x,&y,&z);
		g[x].push_back(P(y,z)); g[y].push_back(P(x,z));
	}
	dfs(1,0);
	printf("%lld\n",ans-mn);
	
	return 0;
}
			

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

int main()
{
  int n;
  cin >> n;
  map<long, long> t;
  long s = 0, count = 0;
  count += t[s];
  t[s]++;
  for (int i = 0; i < n; i++) {
    int cache;
    cin >> cache;
    s += cache;
    count += t[s];
    t[s]++;
  }
  cout << count << endl;
}


Measured memory_bytes: 12800
#include<stdio.h>
#define N 1000

int main(){
  int n, i, j, tmp;
  scanf("%d",&n);
  
  int A[n];
  for(i = 0; i < n; i++) scanf("%d", &A[i]);

  for(j = 0; j < n; j++){
    if(j == n-1) printf("%d",A[j]);
    else printf("%d ",A[j]);
  }
  printf("\n");

  for(i = 1; i < n; i++){
    tmp = A[i];
    j = i - 1;

    while(j >= 0 && A[j] > tmp){
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = tmp;
    
    for(j = 0; j < n; j++){
      if(j == n-1) printf("%d",A[j]);
      else printf("%d ",A[j]);
    }
    printf("\n");
  }

  return 0;
}



Measured memory_bytes: 2728
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> h(N);
  rep(i, N) cin >> h[i];
  int ans = 0;
  rep(i, N) {
    if (h[i] >= K)
      ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<cstdio>
#include<cstring>

using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef string S;
typedef queue<int> qi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
struct edge{ ll to, cost; };//　一つ目は結んでいるノード,二つ目はその辺の重みを指す
//#define sort(a) sort(a.begin(),a.end())
using Graph = vector<vector<edge>>;  //隣接リスト
#define reverse(a) reverse(a.begin(),a.end())
#define pb push_back
#define elif else if
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mp make_pair
#define fr(i,n)for(ll i=0;i<(n);i++)
#define ifr(i,n)for(ll i=(n)-1;i>=0;i--)
#define ALL(a) (a).begin(),(a).end()
const int MOD = 1e9+7;
const ll INF =1e18;

ll n,W;
ll dp[100010];//dp[i]=価値iを手に入れるための最小重さ
int main(){
	scanf("%lld%lld",&n,&W);
	for(ll i = 1;i<100005;++i)dp[i]=INF;
	fr(i,n){
		ll w,v;
		scanf("%lld%lld",&w,&v);
		for(int j=100005-v;j>=0;j--)dp[j+v]=min(dp[j+v],dp[j]+w);
	}
	ll ans=100000;
	while(dp[ans]>W)ans--;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1024
def answerA():
    a, b = map(int, input().split())
    if a < 10 and b < 10:
        result = a * b
    else:
        result = -1

    print(result)


def answerB():
    def can_be_devided_by_1d(n):
        result = 'No'
        for i in range(1,10):
            floor, mod = divmod(n, i)
            if mod == 0 and floor < 10:
                result = 'Yes'
        return result

    n = int(input())
    print(can_be_devided_by_1d(n))


def answerC():
    def make_divisors(n):
        divisors = set()
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.add(i)
                if i != n // i:
                    divisors.add(n // i)
        return divisors

    n = int(input())
    divisors = make_divisors(n)
    candidates = set()

    for i in divisors:
        floor = n // i
        distance = (floor-1) + (i-1)
        candidates.add(distance)

    print(min(candidates))


import math

def answer():
    a, b, x = map(int, input().split())

    bottom = a**2
    volume = bottom * b
    side = a * b

    if x < volume / 2:
        y = 2 * x / side
        radian = math.atan2(b, y)
    elif x > volume / 2:
        y = (2 * x - volume) / a ** 2
        h = b - y
        radian = math.pi / 2 - math.atan2(a, h)
    else:
        radian = math.atan2(b, a)

    print(math.degrees(radian))


if __name__ == '__main__':
    answer()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define lld long long int
#define M 1000000007
#define fors(i,n) for(int i=0;i<n;++i)
#define fore(i,a,b) for(int i=a,i<=b;++i)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define vv vector<int>
#define endl "\n"
#define test(i) cout<<i<<endl
#define itrt int t; cin>>t; fors(i,t)
#define itr1 int t; cin>>t;
#define ff first
#define ss second
#define pb push_back
#define vmp make_pair
#define ppb pop_back
#define sorta(a,n) sort(arr,arr+n)
#define sortv(x) sort(x.begin(),x.end())

int main(){
    fastio;
    int n;
    cin>>n;
    vv x(n);
    vv y(n);
    fors(i,n){
        cin>>x[i]>>y[i];
    }
    double len=0.0;
    fors(i,n){
        fors(j,n){
            len=len+pow(pow(x[i]-x[j],2)+pow(y[i]-y[j],2),0.5);
        }
    }
    printf("%.9f",len/n);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    n=n%10;
    if(n==3)
        cout << "bon" << endl;
    else if(n==0 || n==1 || n==6 || n==8)
        cout << "pon" << endl;
    else
        cout << "hon" << endl;
}


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

int main(void) {
  long long a, b, c;
  cin >> a >> b >> c;
  if (!((a & 1) * (b & 1) * (c & 1))) cout << 0 << endl;
  else {
    long long M = max(a, max(b, c));
    long long m = min(a, min(b, c));
    long long med = a + b + c - m - M;
    cout << m * med << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
# まだ解いてない配点を nokori として持つ
def dfs(i, sum, count, nokori):
    global ans
    if i == d:
        # G 点に満たなければ nokori のうち一番大きいものを解く
        if sum < g:
            use = max(nokori)
            # 解く問題が問題数を超えないように注意
            n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
            count += n
            sum += n * use * 100

        if sum >= g:
            ans = min(ans, count)
    else:
        # 総合スコア、解いた問題数、まだ解いてない問題を更新
        dfs(i + 1, sum, count, nokori)
        dfs(i + 1, sum + pc[i][0] * (i + 1) * 100 + pc[i][1], count + pc[i][0], nokori - {i + 1})


d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float("inf")

dfs(0, 0, 0, set(range(1, d + 1)))
print(ans)

Measured memory_bytes: 9144
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
##########################################
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """
    
    #最短のpathをたす
    
    
    class Edge():
        #重み付き有向辺
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s,g):
        #始点sから頂点iまでの最短経路長のリストを返す
        
        que = [] #priority queue
        d = [float("inf")] * self.V()
        prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
        d[s] = 0
        heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
        
        while len(que)!=0:
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
            if d[v] < cost:
                continue
                
            #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost #更新
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加
        
        #sからgまでの最短経路
        path = []
        pos = g #今いる場所，ゴールで初期化
        for _ in range(self.V()+1):
            path.append(pos)
            if pos == s:
                break
            #print("pos:",format(pos))
            pos = prev[pos]
        path.reverse()
        #print(path)
                    
        return d#,path
########################

def main():
    mod=10**9+7
    N=I()
    djk = Dijkstra(N)
    for _ in range(N-1):
        a,b,c=MI()
        djk.add2(a-1, b-1, c)
        
    Q,K=MI()
    d=djk.shortest_path(K-1,0)
    for _ in range(Q):
        x,y=MI()
        print(d[x-1]+d[y-1])

main()


Measured memory_bytes: 95904
#include <bits/stdc++.h>
#define _boost ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define fi first
#define se second
#define clz __builtin_clz
#define clzll __builtin_clzll
#define bp __builtin_popcount
#define _unique(x) sort((x).begin(),(x).end()),(x).erase(unique((x).begin(), (x).end()),(x.end()))
#define all(x) (x).begin(),(x).end()
#define _rand(i,j) uniform_int_distribution<int>(i, j)(rng___)
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;
typedef pair < LD, LD > PDD;
template < typename _T, typename _T2> string to_string(pair<_T,_T2> x) {return "<"+to_string(x.fi)+", "+to_string(x.se)+">";}
template < typename _T> string to_string(vector<_T> vec) {string s="[ "; for(auto el:vec)s+=to_string(el)+", "; s[s.size()-1]=']';s[s.size()-2]=' '; return s;}
template < typename _T> string to_string(set<_T> vec) {string s="{ "; for(auto el:vec)s+=to_string(el)+", "; s[s.size()-1]='}';s[s.size()-2]=' '; return s;}
template < typename _T, typename _T2> string to_string(map<_T,_T2> vec) {string s="{ "; for(auto el:vec)s+="mp["+to_string(el.fi)+"]= "+to_string(el.se)+", "; s[s.size()-1]='}';s[s.size()-2]=' '; return s;}
template < typename _T > inline void _DBG(const char *s, _T x){cerr << s << " = " << to_string(x) << "\n";}
template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a){while(*s != ',') cerr << *s++;cerr << " = " << to_string(x) << "\n";_DBG(s + 1, a...);}
#ifdef LOCAL
#define _print(...) _DBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define _print(...) ;//cout<<2;//(__VA_ARGS__)
#endif
mt19937 rng___(chrono::steady_clock::now().time_since_epoch().count());


const LL MOD = 998244353;//1e9+7;
const LL LLINF = 1e18+7;
const int N=2e5+8;


int main()
{
    _boost;
    int n;
    cin>>n;
    vector<int> h(n);
    vector<int> dp(n,MOD);
    dp[0]=0;
    for(int i=0;i<n;i++)cin>>h[i];
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<min(i+3,n);j++)
        {
            dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]));
        }
    }
    cout<<dp[n-1];
}




Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>
#include<bitset>
#include<cassert>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

int ok(int x,ll k, vector<int> &a){
	int res = 0;
	rep(i, a.size()) {
		res += (a[i] - 1) / x;
	}
	return res <= k;
}

int main()
{
	string s;
	cin >> s;
	int a = 0;
	rep(i, s.size())
	{
		a += (s[i] - '0');
		a = a % 9;
	}
	if (a == 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;
}

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	
	vector<int> a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	
	int ans1 = *max_element(a.begin(), a.end());
	int ans2 = 0;
	for(int i = 0; i < n; i++)
	{
		if(abs(ans2 - (ans1 / 2)) > abs(a[i] - (ans1 / 2)))
		{
			ans2 = a[i];
		}
	}
	
	cout << ans1 << " " << ans2 << endl;
	return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>
#include <vector>

using namespace std;

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define PB push_back
#define MP make_pair

typedef int64_t ll;
typedef vector<ll> Vl;
typedef pair<ll, int> pli;
using G = vector<vector<pli>>;

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

const ll linf = 1LL << 60;
const ll INF = linf;

template <class Tdist>
void Dijkstra(int org, const G& g, vector<Tdist>& d);

int n;
G g;
Vl d;

void init()
{
	cin >> n;
	g.resize(n);

	REP(_i, n-1)
	{
		int a, b; ll c;
		cin >> a >> b >> c;
		--a; --b;
		g[a].PB(MP(c, b));
		g[b].PB(MP(c, a));
	}
}


int main()
{
	init();

	Dijkstra(0, g, d);

	REP(i, n)
	{
		cout << ((ll)1 & d[i]) << endl;
	}
}


template <class Tdist>
void Dijkstra(int org, const G& g, vector<Tdist>& d)
{
	using P = pair<Tdist, int>;

	vector<bool> done(n, false);
	d.assign(n, INF);
	d[org] = 0;

	priority_queue<P, vector<P>, greater<P>> que;
	que.push(P((Tdist)0, org));

	while (!que.empty())
	{
		Tdist c = que.top().first;
		int v = que.top().second;
		que.pop();
		done[v] = true;

		if (c > d[v])
			continue;

		for (P p : g[v])
			if (!done[p.second] && chmin(d[p.second], c + p.first))
				que.push(P(d[p.second], p.second));
	}
}


Measured memory_bytes: 8704
n = int(input())
a = [int(input()) for _ in range(5)]

import math
print(math.ceil(n/min(a))+4)

# t = [n]
# for _ in range(5 + 1):
#   t.append(0)
# print(a)
# print(t)
# ans = 0
# while t[5] != n:
#   for i in range(5-1,-1,-1):
#     if t[i] >= a[i]:
#       t[i] -= a[i]
#       t[i + 1] += a[i]
#     else:
#       t[i + 1] += t[i]
#       t[i] = 0
#     print(t)
#   print()
#   ans += 1
  
# print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<stdio.h>
#define rep(i,n) for(int i=0; i<n; i++)

using namespace std;

class my_stack{
    private:
        class elem{
            public:
                int value;
                elem* prev;
        };
        elem* back;
    public:
        my_stack(){
            back = NULL;
        }
        void pop(){
            back = back->prev;
        }
        void push(int x){
            elem* e = new elem;
            e->value = x;
            e->prev = back;
            back = e;
        }
        int top(){
            return back->value;
        }
};

string str;
my_stack stk;

void push(string s)
{
    int n = 0;
    rep(i,s.size()) n = n*10 + s[i] - '0';
    stk.push(n);
    return;
}

void push(int n)
{
    stk.push(n);
    return;
}

void add()
{
    int x = stk.top(); stk.pop();
    int y = stk.top(); stk.pop();
    stk.push(x+y);
    return;
}

void subt()
{
    int x = stk.top(); stk.pop();
    int y = stk.top(); stk.pop();
    stk.push(y-x);
    return;
}

void mult()
{
    int x = stk.top(); stk.pop();
    int y = stk.top(); stk.pop();
    stk.push(x*y);
    return;
}

int main(void)
{
    while(cin >> str){
        if(str == "+") add();
        else if(str == "-") subt();
        else if(str == "*") mult();
        else push(str);
    }

    cout << stk.top() << endl;

    return 0;
}




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

using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define vi vector<int>

#define ll long long int

int ctoi(char c) {return c-'0';}
int ord(char c) {return c-'a';}
int len(string s) {return s.length();}
int itoc(int i) {return i+'a';}

int main (){
int N;
cin>>N;
vector<int> v(N);
for(int i=0;i<N;i++) {
    cin>>v[i];
    if(i>0 and i<N-1) {
        if(v[i]>v[i-1] and v[i]>v[i+1]) v[i]--;
    }
}
bool ok = true;
for(int i=0;i<N-1;i++) {
    if(v[i]>v[i+1]) {
        ok = false;
        break;
    }
}
cout<<(ok ? "Yes" : "No")<<endl;
return 0;
}


Measured memory_bytes: 640
import math
targ = int(input())
y,z = 0,0
while True:
    minans = float("inf")
    for n in range(math.ceil(targ ** ( 1 / 3))+1):
        if minans == 0:
            break
        if targ - n**3 >= 0:
            m = int((targ - n**3) **(1/2))
        else:
            m = 0
        if (n ** 3) + (m **2) > targ:
            break
        if minans > targ - (n ** 3 + m**2) + n + m:
            minans = targ - (n ** 3 + m**2) + n + m
    if minans != float("inf"):
        print(minans)
    else:
        print(y + z)
    targ = int(input())
    if targ == 0:
        break
            

Measured memory_bytes: 7924
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,i,p;long double sum=0;
    cin>>n>>m;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
    }
sum=(sum/4.0/m);
    //cout<<sum<<endl;
     i=0;
     p=0;
    while(i<n)
    {
        if(arr[i]>=sum)p++;
        i++;
    }

    cout<<(p>=m?"Yes":"No");
}


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

int main() {
    int n, k;
    cin >> n >> k;
    if ((n-1) * (n-2) / 2 < k) {
        cout << -1 << endl;
    }
    else {
        int d = (n-1) * (n-2) / 2 - k;
        cout << n - 1 + d << endl;
        for (int i = 2; i <= n; ++i) {
            cout << 1 << " " << i << endl;
        }
        int cnt = 0;
        for (int i = 0; i < n-2; ++i) {
            for (int j = i+1; j < n-1; ++j) {
                if (cnt == d) break;
                else {
                    cout << i+2 << " " << j+2 << endl;
                    cnt++;
                }
            }
            if (cnt == d) break;
        }
    }
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int n, m, q, ans;
vector<int> a, b, c, d, A;


void dfs(int depth, int val) {
    if (depth == n) {
        // rep(i, depth) cout << A[i] << " ";
        int current = 0;
        rep(i,q) if(A[b[i]] - A[a[i]] == c[i]) current += d[i];

        ans = max(ans, current);

        return;
    }

    for (int i = val; i <= m; i++) {
        A[depth] = i;
        dfs(depth + 1, i);
    }
}


int main() {
    cin >> n >> m >> q;
    a = b = c = d = vector<int>(q);
    rep(i, q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }

    A = vector<int>(n + 10);

    dfs(0, 1);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3584
n,m=map(int,input().split())
if n==1 and m==1:
  # 1マスのみ
  print(1)
elif n==1 or m==1:
  # 両端:2
  # 中ます:3
  print(max(m-2,n-2))
else:
  # 両端:4
  # 片端:6
  # 中マス:9
  print((n-2)*(m-2))

Measured memory_bytes: 9124
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a[100];
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    for(int i=n-1; i>0; i--){
        cout<<a[i]<<' ';
    }
    cout<<a[0]<<endl;
}


Measured memory_bytes: 3076
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

ll flag[310][310][310];
double dp[310][310][310];
ll n;
double f(ll c1,ll c2,ll c3){
	if(flag[c1][c2][c3])return dp[c1][c2][c3];
	flag[c1][c2][c3]=1;
	if(c1==0&&c2==0&&c3==0){
		dp[0][0][0]=0.0;
		return 0;
	}
	double d=c1+c2+c3;
	double fans=n/d;
	if(c1>0)fans+=f(c1-1,c2,c3)*c1/d;
	if(c2>0)fans+=f(c1+1,c2-1,c3)*c2/d;
	if(c3>0)fans+=f(c1,c2+1,c3-1)*c3/d;
	dp[c1][c2][c3]=fans;
	return fans;
}
int main(){
	cin>>n;
	rep(i,n+1){
		rep(j,n+1){
			rep(k,n+1){
				dp[i][j][k]=0;
				flag[i][j][k]=0;
			}
		}
	}
	map<ll,ll>M;
	rep(i,n){
		ll k;cin>>k;
		M[k]++;
	}
	double ans=f(M[1],M[2],M[3]);
	cout<<fixed<<setprecision(10)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 454912
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
int main() {
    int i,j,k,n,ans=0;
    cin>>n;
    vector<int> c(n),v(n);
    for(i=0;i<n;i++){
        cin>>v[i];
    }
    for(i=0;i<n;i++){
        cin>>c[i];
    }
    for(i=0;i<n;i++){
        ans+=max(0,v[i]-c[i]);
    }
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=-10**9
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):#左下
    minlocal=x[i][0]+x[i][1]
    if minlocal<hidarisita:
        hidarisita=minlocal
    if minlocal==hidarisita:
        hidarisita2=minlocal
for i in range(0,n):#右上
    maxlocal=x[i][0]+x[i][1]
    if maxlocal>migiue:
        migiue=maxlocal
    if maxlocal==migiue:
        migiue2=maxlocal
for i in range(0,n):#右下
    minlocal=-x[i][0]+x[i][1]
    if minlocal<migisita:
        migisita=minlocal
    if minlocal==migisita:
        migisita2=minlocal
for i in range(0,n):#左上
    maxlocal=-x[i][0]+x[i][1]
    if maxlocal>hidariue:
        hidariue=maxlocal
    if maxlocal==hidariue:
        hidariue2=maxlocal
aa=migiue-hidarisita
ab=migiue-hidarisita2
ba=migiue2-hidarisita
bb=migiue2-hidarisita2
cc=hidariue-migisita
cd=hidariue-migisita2
dc=hidariue2-migisita
dd=hidariue2-migisita2
print(max(aa,ab,ba,bb,cc,cd,dc,dd))

Measured memory_bytes: 45360
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#define llint long long
#define mod 1000000007

using namespace std;
typedef pair<llint, llint> P;

llint n;
llint a[300005];
llint cnt[65], beki[65];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	beki[0] = 1;
	for(int i = 1; i < 65; i++) beki[i] = beki[i-1] * 2, beki[i] %= mod;
	
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 62; j++){
			if(a[i] & (1LL<<j)) cnt[j]++;
		}
	}
	
	llint ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 62; j++){
			if(a[i] & (1LL<<j)) ans += (n-cnt[j]) * beki[j] % mod, ans %= mod;
			else ans += cnt[j] * beki[j] % mod, ans %= mod;
		}
	}
	
	ans *= 500000004, ans %= mod;
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e18+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N,M,V,P;
    cin >> N >> M >> V >> P;
    vector<int>A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.rbegin(),A.rend());
    int ans = P;
    int sum = A[P-1];
    for(int i = P; i < N; i++) {
        int cnt = max(0LL,V-(P-1)-(N-i-1)-1);
        cnt *= M;
        if(A[P-1] > A[i]+M) {
            break;
        }
        if(sum+cnt <= (A[i]+M)*(N-(P-1)-(N-i-1)-1)) {
            ans++;
        }
        sum += A[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    ll N;
    cin >> N;
    vector<ll> a(3 * N);
    for (int i = 0; i < 3 * N; i++) {
        cin >> a.at(i);
    }
    sort(a.begin(), a.end());

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += a[N + (i * 2)];
    }
    cout << ans << endl;
}


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

int main(){
  int D,N;
  cin>>D>>N;
  if(D==0){
    if(N != 100){
      cout<<N<<endl;
      return 0;
    }
    else if (N == 100){
      cout<<101<<endl;
      return 0;
    }
  }
  if(D==1){
    if(N !=100){
      cout<<N*100<<endl;
      return 0;
    }
    else if (N==100){
      cout<<10100<<endl;
      return 0;
    }
  }
  
  if(D==2){
    if(N != 100){
      
    cout<<N*10000<<endl;
    return 0;
    }
    else if (N==100){
      cout<<1010000<<endl;
      return 0;
    }
  }
}

       
       

Measured memory_bytes: 3616