akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <unordered_map>
#include <vector>

using edge = std::pair<int, int>;
#define N 100

int main(){
    int n;
    std::scanf("%d", &n);
    std::vector<edge> a[N];
    for(int i = 0; i < n; ++i){
        int id;
        int num;
        std::scanf("%d", &id);
        std::scanf("%d", &num);
        for(int j = 0; j < num; ++j){
            edge e;
            std::scanf("%d", &e.second);//id                                                                                                                                                                                        
            std::scanf("%d", &e.first);//weight                                                                                                                                                                                     
            a[id].push_back(e);
        }
    }
    std::priority_queue<edge, std::vector<edge>, std::greater<edge> > que;
    std::unordered_map<int, int> checked;
    checked.insert(std::make_pair(0, 0));
    for(auto &x: a[0]){
        que.push(x);
    }
    while(checked.size() != n){
        while(checked.find(que.top().second) != checked.end()){
            que.pop();
        }
        edge e = que.top();
        que.pop();
        checked.insert(std::make_pair(e.second, e.first));
        for(auto &x: a[e.second]){
            if(checked.find(x.second) == checked.end()){
                x.first += e.first;
                que.push(x);
            }
        }
    }

    for(int i = 0; i < n; ++i){
        auto x = checked.find(i);
        std::printf("%d %d\n", x->first, x->second);
    }

    return 0;
}



Measured memory_bytes: 2692
n = int(input())

if n == 1:
    print(0)
    exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

s = factorization(n)

ans = 0
for i in s:
    tmp = 0
    c = 0
    while True:
        c += 1
        tmp += c
        if tmp > i[1]:
            break
    ans += c-1
print(ans)




Measured memory_bytes: 9492
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
const int maxn = 13;
int n, m, x;
int c[maxn], a[maxn][maxn];
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> x;
	for (int i = 0;i < n;++i) {
		cin >> c[i];
		for (int j = 0;j < m;++j)
			cin >> a[i][j];
	}
	int res = INT_MAX;
	for (int i = 0;i < (1<<n);++i) {
		vector<int> cnt(m);
		int cost = 0;
		for (int j = 0;j < n;++j)
			if (i&(1<<j)) {
				cost += c[j];
				for (int k = 0;k < m;++k)
					cnt[k] += a[j][k];
			}
		if (*min_element(cnt.begin(), cnt.end()) >= x)
			res = min(res, cost);
	}
	if (res == INT_MAX)
		cout << -1 << '\n';
	else
		cout << res << '\n';
}



Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x;
    cin>>n>>x;
    int a;
    unordered_set<int> s;
    for(int i=0;i<x;i++)
    {
        cin>>a;
        s.insert(a);
    }
    if(s.find(n)==s.end()){
        cout<<n;return 0;
    }
    int i=1;
    while(1){
        if(s.find(n-i)==s.end())
        {
            cout<<n-i;return 0;
        }
        if(s.find(n+i)==s.end()){
            cout<<n+i;return 0;
        }
        i++;
    }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define INF LLONG_MAX
#define Int long long
#define rep(i,n) for(int i=0; i<n; ++i)
using namespace std;
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;}

int main() {
  int N, X; cin >> N >> X;
  vector<int> m(N);
  rep(i,N) cin >> m[i];
  int min=INT_MAX;
  rep(i,N) {
    X -= m[i];
    if(m[i] < min) min = m[i];
  }
  cout << N + X/min << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <math.h>
#include <bits/stdc++.h>
#include <queue>
#include <map>

using namespace std;

#define INF (1ll<<60)
#define INFint (1<<30)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;
typedef pair<ll,ll> P;

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

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

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

// gcd
template<typename T>
T gcd(T a, T b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}

// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);
    return result;
}

template<typename T>
T lcm( T m, T n ){
    // 引数に0がある場合は0を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;
    return ((m/gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}


int dx[5]={1,0,-1,0};
int dy[5]={0,1,0,-1};
// v.front() = -BOUND;
// v.back() = BOUND;

struct edge{
    int cost, to;

    edge(int in_cost, int in_to){
        cost=in_cost;
        to=in_to;
    }
    bool operator<(const edge &a) const
    {
        return cost > a.cost;
    }
};


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

    vector<int>x(N),y(N);
    vector<int>xary,yary;
    ll ans;
    rep(i,N){
        cin >> x[i] >> y[i];
        xary.push_back(x[i]);
        yary.push_back(y[i]);
    }

    sort(xary.begin(), xary.end());
    sort(yary.begin(), yary.end());

    ans= 1LL * (xary[N-1]-xary[0])*(yary[N-1]-yary[0]);
    for(int xi=0; xi<N; xi++){
        for(int xj=xi+1; xj<N; xj++){
            for(int yi=0; yi<N; yi++){
                for(int yj=yi+1; yj<N; yj++){
                    int num=0;
                    ll lx=xary[xi], rx=xary[xj];
                    ll by=yary[yi], uy=yary[yj];

                    for(int i=0; i<N; i++){
                        if(lx<=x[i] and x[i]<=rx and by <= y[i] and y[i] <= uy){
                            num++;
                        }
                    }

                    if(num>=K) ans=min(ans, 1LL*(rx-lx)*(uy-by));
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
Q=int(input())
count=[0]*(10**5+1)
for a in A:
    count[a]+=1

for _ in range(Q):
    b,c=map(int,input().split())
    cnt=count[b]
    if cnt==0:
        print(S)
        continue
    S+=(c*cnt)-(b*cnt)
    print(S)
    count[b]=0
    count[c]+=cnt


Measured memory_bytes: 21060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,i,j,en,to,d[100005],dd[100005],u,v,cg[100005],cv[100005],c[100005]={0},mn,check,cost[200005],co[100005];
bool nol[100005]={0};
vector<pair<ll,ll>> vps;
vector<pair<ll,ll>> g[100005];

int main() {
    // your code goes here
    cin >> n >> m;
    for(i=1;i<=n;i++){
        cin >> dd[i];
        vps.push_back({dd[i],i});
    }
    sort(vps.begin(),vps.end());
    for(i=0;i<n;i++){
        d[i+1]=vps[i].first;
        cg[vps[i].second]=i+1;
        cv[i+1]=vps[i].second;
    }
    if(d[1]!=d[2]){
        cout << -1 << endl; return 0;
    }
    for(i=1;i<=m;i++){
        cin >> u >> v;
        u=cg[u]; v=cg[v];
        if(u>v) swap(u,v);
        if(d[u]==d[v]){
            nol[u]=true; nol[v]=true;
        } else nol[v]=true;
        g[v].push_back({u,i});
    }
    for(i=1;i<=n;i++){
        if(!nol[i]){
            cout << -1 << endl;
            return 0;
        }
        sort(g[i].begin(),g[i].end());
    }
    mn=d[1]; check=0;
    for(i=2;i<=n;i++){
        for(j=0;j<g[i].size();j++){
            to=g[i][j].first; en=g[i][j].second;
            if(c[i]==0){
                if(c[to]==0){
                    c[to]=1; c[i]=-1;
                    cost[en]=d[i];
                } else {
                    c[i]=-c[to];
                    cost[en]=d[i];
                }
            } else {
                if(c[to]==0){
                    c[to]=-c[i];
                    cost[en]=d[i];
                } else {
                    cost[en]=d[i];
                }
            }
        }
    }
    for(i=1;i<=n;i++){
        co[cv[i]]=c[i];
    }
    for(i=1;i<=n;i++){
        if(co[i]==1) cout << "W";
        else cout << "B";
    }
    cout << endl;
    for(i=1;i<=m;i++){
        cout << cost[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 17648
N,M=map(int,input().split())
*A,=map(int,input().split())
BC=[list(map(int,input().split()))[::-1]for _ in range(M)]
BC=sorted(BC)[::-1]

L=[0]
for c,b in BC:
    L+=[c]*b
    if len(L)-1>N:
        break

ans=sorted(A+L)[::-1]
print(sum(ans[:N]))

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

int main() {
    int n, k; cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p.at(i);
    }
    sort(p.begin(), p.end());
    int ans = 0;
    for (int i = 0; i < k; i++) {
        ans += p.at(i);
    }
    cout << ans << endl;
}

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

int main() {
	int input;
	int h, m, s;

	cin >> input;

	h = input / 3600;
	m = (input%3600) / 60;
	s = input - (h*3600) - (m*60);

	cout << h << ':' << m << ':' << s << endl;

	return 0;
}


Measured memory_bytes: 3104
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<cstring>

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define P pair<int, int>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl


/* -- template -- */
const int MAX_N = 101, MAX_W = 3001;
int dp[MAX_N][MAX_N][MAX_W]; //dp[i + 1][j][w] : i番目までみたとき，j個で重さw以下での価値の最大値
int main() {
    int N, W; cin >> N >> W;
    int w[N], v[N];
    rep(i, N) cin >> w[i] >> v[i];
    rep(i, N - 1) w[i + 1] -= (w[0] - 1);
    int tmp = w[0];
    w[0] = 1;
    rep(i, N) {
        rep(j, N){
            rep(ww, MAX_W) {
                dp[i + 1][j + 1][ww] = max(dp[i][j + 1][ww], dp[i + 1][j + 1][ww]);
                if(ww - w[i] >= 0)
                    dp[i + 1][j + 1][ww] = max(dp[i + 1][j + 1][ww], dp[i][j][ww - w[i]] + v[i]);
            }
        }
    }
    int ans = 0;
    rep(j, N) {
        rep(ww, MAX_W) {
            if(ll(j + 1) * (ll(tmp) - 1) + ww <= ll(W))
                ans = max(ans, dp[N][j + 1][ww]);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 118656
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int inf = 1001001001;

int main(){
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;

  int cnt = 0;
  rep(i,n-1){
    if(s[i] == s[i+1]) cnt++;
  }

  int ans = min(cnt+2*k, n-1);
  cout << ans << endl;
}


Measured memory_bytes: 3756
N,x=map(int,input().split())
A=list(map(int,input().split()))

count=0
for i in range(0,N-1):
    if A[i]>x:
        count+=A[i+1]+A[i]-x
        A[i+1]=0
    elif A[i]+A[i+1]>x:
        count+=A[i]+A[i+1]-x
        A[i+1]-=A[i]+A[i+1]-x

print(count)


Measured memory_bytes: 63984
n, m, x = map(int, input().split())

c = []
for i in range(n):
    c.append([int(x) for x in input().split()])

min_cost = float('inf')

for i in range(2**n):
    cost = []
    ex = [0]*m
    for j in range(n):
        if (i>>j) & 1 == 1:
            cost.append(c[j][0])
            for k in range(1, m+1):
                ex[k-1] += c[j][k]
    flag = 1
    for l in range(len(ex)):
        if ex[l] < x:
            flag = 0
    if flag == 1:
        min_cost = min(min_cost, sum(cost))

if min_cost == float('inf'):
    print("-1")
else:
    print(min_cost)


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

int main() {
	// your code goes here
    long long int a, b;
    long long int mul = 0;
    scanf("%lld %lld", &a, &b);
    for(int i = 1; i <= b; i++)
    {
        mul = a * i;
        //cout << mul;
        if(mul % b == 0)
        {
            printf("%lld", mul);
            break;
        }
    }
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long n, q, b, c,g;
  long long ans=0;
  cin >> n;
  vector<long long> a(10000000);
  for(long long i=1;i<=n;i++){
    cin >> g;
    a[g]++;
  }
  cin >> q;
  for(long long j=1;j<=a.size();j++){
    ans += a[j] * j;
  }
  
  for(long long i=1;i<=q;i++){
    cin >> b >> c;
    ans -= a[b] * b;
    ans -= a[c] * c;
    a[c] += a[b];
    a[b] = 0;
    ans += a[b] * b;
    ans += a[c] * c;
    cout << ans << endl;
  }
  
  
  
}

Measured memory_bytes: 81404
/* Author: topcoderme123
   Date: 22nd june 2020 
*/

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mod 1000000007
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
#define np next_permutation
using namespace std;
using vi=vector<int>;
#define lp(i,n) for(int i=0;i<n;i++)
#define reps(i,j,n) for(int i=j;i<=n;i++)
#define vii vector<vi>
#define vb vector<bool>
#define pr pair<int,int>
#define vl vector<ll>
#define vs vector<string>
#define us unordered_map<int,int>
#define Mpq priority_queue<int>
#define mpq priority_queue<int,vi,greater<int>> 
#define eb emplace_back
#define prl pair<ll,ll>
#define vp vector<pr>
const int N=(int)2e5+11;

int n;
ll Xor;
ll a[N];
void solve(){
    cin>>n;
    lp(i,n){
      cin>>a[i];
      Xor=(!i)?a[i]:(a[i] xor Xor);
    }
    lp(i,n) cout<<(Xor xor a[i])<<" ";
    cout<<"\n";
}
    
int main(int argc,char *argv[]){
   ios_base::sync_with_stdio(0);
   cin.tie(nullptr);
   solve();
   return 0;
}


Measured memory_bytes: 5180
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <utility>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;

int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    double sum=0;
    for(int i=0;i<n;i++)
    {
        sum+=(double)1/a[i];
    }
    sum=1/sum;
    printf("%.7lf\n",sum);
    
}


Measured memory_bytes: 256
alp = [chr(ord("A")+i) for i in range(26)]
n = int(input())
s = input()

for i in range(len(s)):
    x = alp.index(s[i])
    if x + n >= 26:
        print(alp[x+n-26],end="")
    else:
        print(alp[x+n],end="")

Measured memory_bytes: 4468
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;




int main(){

	int N,M;

	scanf("%d %d",&N,&M);

	vector<int> V;

	int ans = -1;

	for(int i = 1; i*i <= M; i++){
		if(M%i != 0)continue;

		if(i >= N){

			ans = max(ans,M/i);
		}
		if(M/i >= N){

			ans = max(ans,i);
		}
	}

	printf("%d\n",ans);

	return 0;
}


Measured memory_bytes: 3736
n = gets.to_i
arr = []

mx = {index:0, value:0}
mx_2 = {index:0, value:0}

n.times do |i|
  input = gets.to_i
  if input > mx[:value]
    mx_2[:index] = mx[:index]
    mx_2[:value] = mx[:value]
    mx[:index] = i
    mx[:value] = input
  elsif input > mx_2[:value]
    mx_2[:index] = i
    mx_2[:value] = input
  end
  arr << input
end


n.times do |i|
  puts (i == mx[:index]) ? mx_2[:value] : mx[:value]
end

Measured memory_bytes: 5172
/**********************************************
 * author : deepak nayan
 * file   : e:/Solutions/atcoder/abc101_a.cpp
 * time   : Thu Apr 30 21:36:14 2020
 * quest  : A - Eating Symbols Easy
 *********************************************/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  cout << 0 + (s[0] == '-' ? -1 : 1) + (s[1] == '-' ? -1 : 1) + (s[2] == '-' ? -1 : 1) + (s[3] == '-' ? -1 : 1) << "\n";
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
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; }


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


Measured memory_bytes: 256
# input
N, Y = map(int, input().split())

def solve():
    y = Y//1000
    if Y%1000 != 0:
        print('-1 -1 -1')
        return

    flag = False
    for i in range(2*10**3+1):
        for j in range(10**3+1):
            if y - 10*i - 5*j == N - i - j and N-i-j >= 0:
                print(i, j, N - i - j)
                return

    print('-1 -1 -1')


if __name__ == "__main__":
    solve()


Measured memory_bytes: 39792
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

class Combination():
    # コンストラクタ
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P

        # fact[i] = (i! mod P)
        self.fact = [1, 1]   
        # factinv[i] = ((i!)^(-1) mod P)
        self.factinv = [1, 1]
        # factinv 計算用
        self.inv = [0, 1]    

        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    # nCk (mod P)   (ただし、n<=N)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] * self.factinv[n-k] % self.P

def main():
    N,K = map(int,input().split())
    A = sorted([int(i) for i in input().split()])

    mod = 10**9+7

    COMB = Combination(N,mod)

    cmb = [0] * (N-K+1)
    for i in range(N-K+1):
        cmb[i] = COMB.getComb(i+(K-1),K-1)

    sum_max = 0
    for i in range(K-1,N):
        sum_max = (sum_max + cmb[i-(K-1)] * A[i]) % mod

    sum_min = 0
    for i in range(N-K,-1,-1):
        sum_min = (sum_min + cmb[(N-K)-i] * A[i]) % mod

    answer = sum_max - sum_min
    print(answer % mod)

if __name__ == "__main__":
    main()

Measured memory_bytes: 22424
#include <stdio.h>

int main(void)
{
	int a[3],b[3] = {0,0,0},c[3];
	int i;
	
	scanf("%d%d%d",&a[0],&a[1],&a[2]);
	
	if(a[0] > a[1]){
		b[0]++;
	}else{
		b[1]++;
	}
	
	if(a[0] > a[2]){
		b[0]++;
	}else{
		b[2]++;
	}
	
	if(a[1] > a[2]){
		b[1]++;
	}else{
		b[2]++;
	}
	
	for(i = 0;i < 3;i++){
		c[b[i]] = a[i];
	}
	for(i = 0;i < 3;i++){
   		if(i < 2){
   			printf("%d ",c[i]);
   		}else{
   			printf("%d\n",c[i]);
   		}
	}
	return 0;
}

Measured memory_bytes: 596
def main():
    n, m = map(int, input().split())
    a = sorted(int(i) for i in input().split())
    bc = [(0, 0) for _ in range(m)]
    for i in range(m):
        b, c = map(int, input().split())
        bc[i] = (c, b)
    bc.sort(reverse=True)
    k = 0
    d = []
    for c, b in bc:
        if k + b > n:
            d += [c] * (n - k)
            break
        d += [c] * b
        k += b
    for i in range(len(d)):
        if a[i] < d[i]:
            a[i] = d[i]
        else:
            break
    print(sum(a))


if __name__ == '__main__':
    main()


Measured memory_bytes: 28108
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = numeric_limits<ll>::max()/3;

int main(void){
  int n;
  int res = 0;
  int prev = 0;
  int cont = 0;
  cin >> n;
  for(int i = 0;i < n;++i){
    int now;
    cin >> now;
    if(now != prev){
      res += cont/2;
      cont = 1;
      prev = now;
    }else{
      ++cont;
    }
  }
  res += cont/2;
  cout << res << endl;
  return 0;
}



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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 30)
#define MOD 1000000007
//int dy[4] = {-1,0,0,1};
//int dx[4] = {0,1,-1,0};



int main(){

  int a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << min(a,b) + min(c,d) << endl;


  

  return 0;
}


Measured memory_bytes: 256
// **** WHEN THE GOING GETS TOUGH, THE TOUGH GETS GOING. ****

#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;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >
//added two more functions to set
//(1)*(set.find_by_order(k))[kth element in the sorted set] 
//(2)set.order_of_key(k)[count of elements strictly less than k]

typedef vector< int > vi;
typedef vector< ll > lvi;
typedef vector< vi > vvi;
typedef vector< lvi > lvvi;
typedef pair< int,int > ii;
typedef pair< ll,ll > lii;
typedef vector<ii> vii;
typedef vector<lii> lvii;

#define min_prq(t) priority_queue<t,vector<t>,greater<t>>
#define max_prq(t) priority_queue<t>
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)//remember i is an iterator
#define present(c,x) ((c).find(x) != (c).end())//for sets,maps,multimaps
#define cpresent(c,x) (find(all(c),x) != (c).end())//for vectors
#define tc(t) int (t); cin>>(t);while((t)--)
#define ff first
#define ss second
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " is " << a << endl;
	err(++it, args...);
}

//-----------------------------------------------------------------------------------------------------------------------------------------------------------------
#define mod 1000000007
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------

ll mod_sum() { return 0LL; }
template<typename T, typename... Args>
T mod_sum(T a, Args... args) { return ((a + mod_sum(args...))%mod + mod)%mod; }

ll mod_product() { return 1LL; }
template<typename T, typename... Args>
T mod_product(T a, Args... args) { return (a*mod_product(args...))%mod; }
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------
lvvi dp,adj;
ll dfs(ll x,ll state,ll par=-1)
{
	if(dp[x][state]!=-1) return dp[x][state];
	if(adj[x].size()==1 && adj[x][0]==par){
		dp[x][state]=1;
		return 1;
	}
	ll val=1;
	for(auto next:adj[x])
	{
		if(next!=par)
		{
			if(state==0) // white
			{
				val=mod_product(val,mod_sum(dfs(next,0,x),dfs(next,1,x)));
			}
			else // black
			{
				val=mod_product(val,dfs(next,0,x));
			}
		}
	}
	dp[x][state]=val;
	// error(x,state,dp[x][state]);
	return val;
}

signed main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);	
	ll n;
	cin>>n;
	adj.resize(n+2);
	dp.assign(n+2,lvi(3,-1));
	for (int i = 0; i < n-1; ++i)
	{
		ll x,y;
		cin>>x>>y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	cout<<mod_sum(dfs(1,0),dfs(1,1))<<endl;
	return 0;
}

Measured memory_bytes: 20992
#!python
# -*- coding: utf-8 -*-

A, B, K = list(map(int, input().split(' ')))

out = [i for i in range(A, min(A + K, B + 1))]
out += [i for i in range(max(B - K + 1, A + K), B + 1)]

print(*out, sep='\n')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

int32_t main(){
	IOS;
	int k, x;
	cin >> k >> x;
	int ans = k * 500;

	if(ans >= x)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;	




	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
using namespace std;
int main()
{
    int n;
    int k;
    cin>>n>>k;
    deque<long long int> d;
    long long int v;
    for(int i=0;i<n;i++){
        cin>>v;
        d.push_back(v);
    }
    deque<long long int> d_copy;
    d_copy=d;
    //操作は取り出しを完了させてから詰めて構わない。
    //言い換えれば取り出し回数ごとにK^3ordくらいでしらべる。
    int l;//取り出し回数
    if(k%2==0){l=k/2;}
    else{l=(k+1)/2;}
    if(l>n){l=n;}
    vector<long long int> v_n;
    int b;//戻し回数
    long long int max=0;//取り出しパターンにおける最大値
    long long int sum=0;
    int s;
    while(l<=k&&l<=n){
        b=k-l;
        //取り出しパターンl+1通りの精査(k*(Klogk)ord)
        for(int i=0;i<l+1;i++){
            for(int j=0;j<i;j++){
                v=d.front();
                d.pop_front();
                v_n.push_back(v);
            }
            for(int j=0;j<l-i;j++){
                v=d.back();
                d.pop_back();
                v_n.push_back(v);
            }
            sort(v_n.begin(),v_n.end());
            reverse(v_n.begin(),v_n.end());
            sum=0;
            for(int j=0;j<b;j++){
                if(!v_n.empty()){
                    if(v_n.back()<=0){
                       v_n.pop_back();
                    }
                }
            }
            s=v_n.size();
            for(int j=0;j<s;j++){
                sum=sum+v_n.back();
                v_n.pop_back();
            }
            if(sum>max){max=sum;}
            /*cout<<max<<endl;*/
            sum=0;
            v_n.clear();
            d=d_copy;
        }
        l++;
    }
    cout<<max<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;


vector<ll> g[200010];
ll tree[200010],c[200010],m[200010];
const ll MOD=1000000007;

void dfs(ll v,ll p){
   tree[v]=1LL;
   for(ll i=0;i<(ll)g[v].size();i++){
     if(g[v][i]!=p) dfs(g[v][i],v);
   }
   tree[p]+=tree[v];
   c[p]+=(m[tree[v]]-1LL+MOD)%MOD;
}

ll extgcd(ll a,ll b,ll &x,ll &y){
	ll g;
	if(b!=0LL){
		g=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}else{
                g=a;
		x=1LL; y=0LL;
	}
	  return g;
}

ll mod_inverse(ll a,ll M){
    ll x,y;
    extgcd(a,M,x,y);
    return (x%M+M)%M;
}

int main(void){
	          ll i;

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

	          ll N;
	          cin >> N;
	          for(i=0;i<N-1;i++){
	        	  ll a,b;
	        	  cin >> a >> b;
	        	  a--;
	        	  b--;
	        	  g[a].push_back(b);
	        	  g[b].push_back(a);
	          }

	          m[0LL]=1LL;
	          for(i=1;i<=N;i++) m[i]=(2*m[i-1LL])%MOD;

	          dfs(0LL,-1LL);

	          ll y=0;
	          for(i=0;i<N;i++){
	        	  ll d=(c[i]+m[N-tree[i]]-1LL+MOD)%MOD;
	        	  d++;
	        	  ll s=(m[N-1LL]-d+MOD)%MOD;
	        	  y=(y+s)%MOD;
	          }

	          ll xx=mod_inverse(m[N],1000000007);
	          ll z=(y*xx)%MOD;

	          cout << z << endl;

	          return 0;
}


Measured memory_bytes: 22912
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<bitset>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<numeric>
using namespace std;

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

#define rep(i,x) for(int i=0;i<x;i++)
#define re(i,x,y) for(int i=x;i<y;i++)

long long INF=1e9;
const long long mod=2019;
#define ll long long

int H,W;
vector<vector<int>>field;
void dfs(int h,int w){
  field[h][w]=0;
  for(int dh=-1;dh<=1;dh++){
    for(int dw=-1;dw<=1;dw++){
      int nh=h+dh,nw=w+dw;
      if(nh<0||nh>=H||nw<0||nw>=W)continue;
      if(field[nh][nw]==0)continue;
      dfs(nh,nw);
    }
  }
}

int main(){
  while(cin>>W>>H){
    if(H==0||W==0)break;
    field.assign(H,vector<int>(W,0));
    for(int h=0;h<H;h++){
      for(int w=0;w<W;w++){
        cin>>field[h][w];
      }
    }
    int count=0;
    for(int h=0;h<H;h++){
      for(int w=0;w<W;w++){
        if(field[h][w]==0)continue;
        dfs(h,w);
        count++;
      }
    }
    cout<<count<<endl;
  }
}


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

using ll = long long;

ll A[100001];
ll dp[2][2][100001];

int main() {
	int n;
	while (cin >> n) {
		for (int i = 0; i < n; ++i) {
			cin >> A[i];
		}
		dp[0][0][0] = dp[1][0][0] = A[0];
		dp[0][1][0] = dp[1][1][0] = -A[0];
		
		for (int i = 1; i < n; ++i) {
			dp[0][0][i] = max(dp[0][0][i-1] + A[i], dp[1][0][i-1] + A[i]);
			dp[1][0][i] = max(dp[0][1][i-1] - A[i], dp[1][1][i-1] - A[i]);
			dp[0][1][i] = max(dp[0][0][i-1] - A[i], dp[1][0][i-1] - A[i]);
			dp[1][1][i] = max(dp[0][1][i-1] + A[i], dp[1][1][i-1] + A[i]);
		}
		
		cout << max(dp[0][0][n-1], dp[1][0][n-1]) << endl;
	}
	return 0;
}

Measured memory_bytes: 4096
#include<stdio.h>

int main()
{
	int N,M,A[1005],B,i,j,V[1005]={0};
	scanf("%d%d",&N,&M);
	for(i=0;i<N;i++)scanf("%d",&A[i]);
	for(i=0;i<M;i++)
	{
		scanf("%d",&B);
		for(j=0;A[j]>B;j++);
		V[j]++;
	}
	for(i=B=0;i<N;i++)B=V[i]>V[B]?i:B;
	printf("%d\n",B+1);
	return 0;
}

Measured memory_bytes: 604
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
const int MOD=1e9+7;
 
vector<pair<int,int>> vectorCnt(vector<int> a) {
    sort(a.begin(),a.end());
    int n=a.size();
    vector<pair<int,int>> b;
    int cnt=1;
    rep(i,n-1) {
            if (a[i+1]!=a[i]) {
                b.push_back(make_pair(a[i],cnt));
                cnt=1;
            } else {
                ++cnt;
            }
    }
    b.push_back(make_pair(a[n-1],cnt));
    return b;
}


int main() {
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<pair<int,int>> p=vectorCnt(a);
    int ans=0;
    rep(i,p.size()) {
        if (p[i].second%2==1) ++ans;
    }
    cout << ans << endl;

    return 0;
}

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

int main(){
  ll dp[110][100100];
  ll n, w;
  cin >> n >> w;
  vector<int> weight(n);
  vector<int> value(n);
  rep(i,n) cin >> weight[i] >> value[i];
  rep(i,n){
    rep(j,w+1){
      if(j - weight[i] >= 0) dp[i+1][j] = max(dp[i+1][j], dp[i][j - weight[i]] + value[i]);
      dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
    }
  }
  cout << dp[n][w] << endl;
}

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

def main():
    n, m = map(int, input().split())
    ans = 1
    for i in range(1, int(m**0.5)+1):
        if m % i == 0:
            if m >= i * n:
                ans = max(ans, i)
            if m >= (m // i) * n:
                ans = max(ans, m // i)
    print(ans)
    
if __name__ == '__main__':
    main()

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

int mhdist(int x1, int y1, int x2, int y2);

int main(){
  int N, nx, ny, nt, px=0, py=0, pt=0;
  cin >> N;
  for(int i=0; i<N; i++){
    cin >> nt >> nx >> ny;
   	int npdist = mhdist(px, py, nx, ny), tdist = nt-pt;
    if(npdist > tdist || (tdist-npdist)%2 != 0){
      cout << "No";
      return 0;
    }
    px=nx;
    py=ny;
    pt=nt;
  }
  cout << "Yes";
  return 0;
}

int mhdist(int x1, int y1, int x2, int y2){
  return abs(x2-x1)+abs(y2-y1);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(long long int i=a; i<b; i++ )
#define REP(i,n) rep(i,0,n)
struct edge{ int u, v, cost; };
struct DirectedGraph
{
  int vertex_num;
  int edge_num;
  vector<edge> edge_list;
  vector< vector<int> > adj_list;
};


void displayVector(vector<int> v)
{
	int n = v.size();
	REP(i,n){
		cout << v[i]+1 << " " ;
	}
	cout << endl;
}

vector<int> bfs(vector< vector<int> > adj_list, int start){
  int N = adj_list.size(); // Number of Vertex
  queue<int> que;
  vector<int> dist(N, -1); // distance
  vector<int> prev(N,-1);

  // init
  dist[start] = 0;
  que.push( start );
  
  // main loop
  while( !que.empty() ){
    int v = que.front(); que.pop();
    
    REP(i, adj_list[v].size()){
      int nv = adj_list[v][i];
      if(dist[nv] != -1) continue;
      
      dist[nv] = dist[v] + 1;
			prev[nv] = v;
      que.push(nv);
    }
  }
  
  return prev;
}

int main(){
	DirectedGraph G;
  cin >> G.vertex_num >> G.edge_num;
  G.adj_list.resize(G.vertex_num);

	int tmp1,tmp2;
  REP(i, G.edge_num){
		cin >> tmp1 >> tmp2;
		G.adj_list[tmp1-1].push_back(tmp2-1);
		G.adj_list[tmp2-1].push_back(tmp1-1);
  }

	vector<int> res = bfs(G.adj_list, 0);
	// displayVector(res);

	int jud = 1;
	REP(i, res.size()-1){
		if( res[i+1] == -1){ jud = 0; }
	}

	if( jud==1 ){
		cout << "Yes" << endl;
		REP(i, res.size()-1){ cout << res[i+1]+1 << endl;}
	} else {cout << "No" << endl; }

	return 0;
}

Measured memory_bytes: 16456
#include<stdio.h>
#define N 10000

int main(void){
  int i,num,j;
  int am,re;
  int count[N];

  for(i=0;;i++){
    scanf("%d",&am);
    if(am==0) break;

    count[i]=0;
    re=1000;
    re-=am;

    if(re>=500){ count[i]++; re-=500; }

    for(j=4;j>=1;j--)
      if(re>=j*100){ count[i]+=j; re-=j*100; break; }

    if(re>=50){ count[i]++; re-=50; }

    for(j=4;j>=1;j--)
      if(re>=j*10){ count[i]+=j; re-=j*10; break; }

    if(re>=5){ count[i]++; re-=5; }

    for(j=4;j>=1;j--)
      if(re>=j*1){ count[i]+=j; break; }
  }

  num=i;

  for(i=0;i<num;i++)
    printf("%d\n",count[i]);

  return 0;
}

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

int main() {
  string s,t;
  cin >> s >> t;
  int ans = 0;
  for (int i = 0;i < 3;i++){
    if (s[i] == t[i]){
      ans++;
    }
  }
  
  cout << ans << endl;
}



Measured memory_bytes: 3600
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 100000000
#define INF 300000000000000000
#define MOD 1000000007
#define mod 1000000007
#define INT_MAX_ 2147483647
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define rep(i,n)for (ll i = 0; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
#define me memset
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp1(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //-------------------------------
    ll n,a,b;cin>>n>>a>>b;
    V<ll>h(n);
    for(ll i=0;i<n;i++)cin>>h[i];
    ll l=0,r=1000000000;
    ll mid=0;
    while(l<r-1){
        mid=(l+r)/2;
        ll B_damage = b*mid;
        ll cnt=0;
        for(ll i=0;i<n;i++){
            ll c=h[i]-B_damage;
            if(c>0){
                cnt+=(c+a-b-1)/(a-b);
            }
        }
        if(cnt<=mid)r=mid;
        else l=mid;
        //cout<<mid<<endl;
    }

    cout<<r<<endl;
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------





































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


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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t,u;
  int a,b;
  cin>>s>>t;
  cin>>a>>b;
  cin>>u;

  if(s==u){
    a--;
  }
  if(t==u){
    b--;
  }
  cout<<a<<' '<<b<<"\n";
  return(0);
}



Measured memory_bytes: 256
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
	s = chomp(readline())
	r = 0
	b = 0
	for i in 1:length(s)
		if s[i] == '0'
			r += 1
		else
			b += 1
		end
	end
	println(length(s)-abs(r-b))
end
main()

Measured memory_bytes: 169988
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

#define MAX 20

double L[MAX],a[MAX],b[MAX];

double calc(int x,int y){
  return pow(L[x]-L[y],2)+pow(a[x]-a[y],2)+pow(b[x]-b[y],2);
}

int main(){
  int N,M;
  cin >> N >> M;
  for(int i = 0 ; i < N ; i++){
    cin >> L[i] >> a[i] >> b[i];
  }
  double ans = 0;
  for(int S = 0 ; S < 1<<N ; S++){
    if(__builtin_popcount(S) == M){
      double dist = 0;
      vector<int> vec;
      for(int i = 0 ; i < N ; i++){
        if(!(S >> i & 1)) continue;
        vec.push_back(i);
      }
      for(int i = 0 ; i < M ; i++){
        for(int j = i+1 ; j < M ; j++){
          dist += calc(vec[i],vec[j]);
        }
      }
      ans = max(ans,dist);
    }
  }
  printf("%.10f\n",ans);

  return 0;
}

Measured memory_bytes: 1268
#include <iostream>
#include <algorithm>
#include <cassert>
#include <climits>
using namespace std;
 
const int MAX = 1000000;
 
int main(){
  long long n, x, sum = 0, maxi = -MAX, mini = MAX;
  cin >> n;
  //  assert(n <= 10000);
  for(int i=0;i<n;i++){
    cin >> x;
    maxi = max(maxi, x);
    mini = min(mini, x);
    //assert((long long)sum + (long long)x < INT_MAX);
    sum += x;
  }
  cout << mini << ' ' << maxi << ' ' << sum << endl;
}

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

#define MOD 1000000007
#define ll long long int 
#define off ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

ll dp[3000][3000];

int main()
{
    off;

    int n;cin>>n;
    ll arr[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>arr[i];
    }

    for (int i = 0; i < n; ++i)
    {
        dp[i][i] = arr[i];
    }

    for (int i = 1; i < n; ++i)
    {
        for (int j = 0; j < n && j+i<n; ++j)
        {
            dp[j][j+i] = max(arr[j]-dp[j+1][j+i], -dp[j][j+i-1]+arr[j+i]);
        }
    }

    cout<<dp[0][n-1];

    return 0;
}


Measured memory_bytes: 70016
#include <iostream>
#include <cmath>

using namespace std;

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

int main() {

    int N, a;
    scanf("%d", &N);

    int ans = 32767;
    int tmp = 0;

    REP(i, N){
        scanf("%d", &a);
        tmp  = 0;
        REP(j, ans){
            if(a % 2 == 0){
                a   /= 2;
                tmp  = j + 1;
            } else {
                break;
            }
        }
        ans = min(ans, tmp);
    }

    printf("%d\n", ans);
}


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

int main()
{
	int A,B;
	while(cin >> A >> B, (A||B))
	{
		int a[3]={1000,500,100},r[3], C=B-A;
		for(int i=0; i<3; i++)
		{
			r[i]=C/a[i];
			C%=a[i];
		}
		for(int i=0; i<3; i++)
		{
			if(i!=0) cout << " ";
			cout << r[2-i];
		}
		
		cout << endl;
	}
}

Measured memory_bytes: 0
N, M = map(int, input().split())
students = [tuple(map(int,input().split())) for i in range(N)]
cps = [tuple(map(int,input().split())) for i in range(M)]

def manlen(a,b) :
  return abs(a[0]-b[0])+abs(a[1]-b[1])

for std in students:
  lengths = [manlen(std,cp) for cp in cps]
  bestcp = 1 + lengths.index(min(lengths))
  print(bestcp)

Measured memory_bytes: 3064
#include <iostream>
#define e 0.00000001
using namespace std;
void func(int,int,double,int);
int p,q,a,n,cnt;
double k;
 
int main(){
  while(1){
    cin>>p>>q>>a>>n;
    if(!p&&!q&&!a&&!n) break;
    k=1.0*p/q;
    cnt=0;
    func(0,1,0,1);
    cout<<cnt<<endl;
  }
  return 0;
}
 
void func(int x,int w,double y,int I){
  if(-e<=k-y&&k-y<=e) cnt++;
  if(x==n) return ;
  for(int i=I;w*i<=a;i++){
    if(y+1.0/i>k+e) continue;
    func(x+1,w*i,1.0/i+y,i);
  }
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
int h,w,d;
string mp[101];
int dx[]={0,1};
int dy[]={1,0};

int check(int y,int x,int i){
  int cnt=0;
  while(mp[y][x]=='.'){
    cnt++;
    if(cnt==d) return 1;
    x+=dx[i];
    y+=dy[i];
    if(x<0||x>=w||y<0||y>=h)return 0;
    
  }
  return 0;

}


int main(){

  cin>>h>>w>>d;
  for(int i=0;i<h;i++) cin>>mp[i];

  int ans=0;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      ans+=check(i,j,0)+check(i,j,1);
  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 3160
#include<bits/stdc++.h>
using namespace std;
#include <climits>
#define Sheryang main
typedef long long ll;
#pragma GCC optimize(3)
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y) {
	return x>y?y:x;
}
template<class T> inline T max(T &x,const T &y) {
	return x<y?y:x;
}
int read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct ios {
	inline char gc() {
		static const int IN_LEN=1<<18|1;
		static char buf[IN_LEN],*s,*t;
		return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
	}
	template <typename _Tp> inline ios & operator >> (_Tp&x) {
		static char ch,sgn;
		ch = gc(), sgn = 0;
		for(; !isdigit(ch); ch=gc()) {
			if(ch==-1)return *this;
			sgn|=ch=='-';
		}
		for(x=0; isdigit(ch); ch=gc())x=(((x<<2)+x)<<1)+(ch^'0');
		sgn&&(x=-x);
		return *this;
	}
} io;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
/** keep hungry and keep calm! **/

int x,y,ans;
int res(int x,int y)
{
	if(x <= y)	return y-x;
	else	return x-y+2;
}
int main()
{
	cin >> x >> y;
	ans = min(res(x,y),min(res(-x,y)+1,min(res(x,-y)+1,res(-x,-y)+2)));
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        String s=sc.next();
        int finalans=s.length()-s.replaceAll("E","").length()-(s.charAt(0)=='E'?1:0);
        int tmp=finalans;
        for(int i=0;i<n-1;i++){
            if(s.charAt(i)=='W')tmp++;
            if(s.charAt(i+1)=='E')tmp--;
            finalans=Math.min(tmp,finalans);
        }
        System.out.println(finalans);

    }
}

Measured memory_bytes: 44824
#include <iostream>
using namespace std;
int main()
{
    int a, b, c;
    while(cin>>a>>b>>c){
        if(a==b&&a==c){
            cout<<1<<endl;
        }
        else if(a==b||a==c||b==c){
            cout<<2<<endl;
        }
        else cout<<3<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
using Yorukatsu022.Questions;
using Yorukatsu022.Extensions;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Yorukatsu022.Questions
{
    /// <summary>
    /// ABC089 A
    /// </summary>
    public class QuestionA : AtCoderQuestionBase
    {
        public override IEnumerable<object> Solve(TextReader inputStream)
        {
            yield return inputStream.ReadInt() / 3;
        }
    }
}


namespace Yorukatsu022
{
    class Program
    {
        static void Main(string[] args)
        {
            IAtCoderQuestion question = new QuestionA();    // 問題に合わせて書き換え
            var answers = question.Solve(Console.In);
            foreach (var answer in answers)
            {
                Console.WriteLine(answer);
            }
        }
    }
}

#region Base Classes

namespace Yorukatsu022.Questions
{

    public interface IAtCoderQuestion
    {
        IEnumerable<object> Solve(string input);
        IEnumerable<object> Solve(TextReader inputStream);
    }

    public abstract class AtCoderQuestionBase : IAtCoderQuestion
    {
        public IEnumerable<object> Solve(string input)
        {
            var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
            var reader = new StreamReader(stream, Encoding.Unicode);

            return Solve(reader);
        }

        public abstract IEnumerable<object> Solve(TextReader inputStream);
    }

}

#endregion

#region Extensions

namespace Yorukatsu022.Extensions
{
    internal static class TextReaderExtensions
    {
        internal static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
        internal static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
        internal static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
        internal static string ReadString(this TextReader reader) => reader.ReadLine();

        internal static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
        internal static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
        internal static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
        internal static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
    }
}

#endregion

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

int main() {
    int ans = 0;
    int N;
    cin >> N;
    vector<int> H(N);
    for(int i = 0; i < N; i++) {
        cin >> H[i];
    }
    int Count = 0;
    for(int i = 0; i < N - 1; i++) {
        if(H[i] >= H[i + 1])
            Count++;
        else {
            ans = max(ans, Count);
            Count = 0;
        }
    }
    ans = max(ans, Count);

    cout << ans << endl;
}

Measured memory_bytes: 3700