akhauriyash/Code-Regression huggingface dataset:
//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10 , MOD = 1e9 + 7;
vector<int> adj[MAXN];
int p[MAXN];
bool mark[MAXN];
int main(){
	ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);
        int n , m , u , v;
        cin >> n >> m;
        for(int i = 0 ; i < m ; i++){
                cin >> u >> v;
                u--;v--;
                adj[u].push_back(v);
                adj[v].push_back(u);
        }
        queue <int> q;
        q.push(0);
        while(q.size()){
                int f = q.front();
                q.pop();
                for(int i : adj[f]){
                        if(mark[i]) continue;
                        mark[i] = 1;
                        q.push(i);
                        p[i] = f;
                }
        }
        for(int i = 0 ; i < n ; i++) if(!mark[i]) return cout << "No\n" , 0;
        cout << "Yes\n";
        for(int i = 1 ; i < n ; i++){
                cout << ++p[i] << '\n';
        }
}


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

const int MX = 1e5+5;
vector<int> adj[MX];
int dp[MX];
bool vt[MX];
int ti;
int sorted[MX];
int ans;

void tsort(int u){
	vt[u] = 1;
	for(int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i];
		if(!vt[v]){
			tsort(v);
		}
	}
	sorted[ti--] = u;
}


int main(){
	int n, m;
	cin >> n >> m;
	ti = n;
	for(int i = 0; i < m; i++){
		int x,y;
		cin >> x >> y;
		adj[x].push_back(y);
	}
	
	for(int i = 1; i <= n; i++){
		if(!vt[i]) tsort(i);
	}
	
	for(int i = 1; i <= n; i++){
		int u = sorted[i];
		for(int j = 0; j < adj[u].size(); j++){
			int v = adj[u][j];
			dp[v] = max(dp[v], dp[u]+1);
			ans = max(ans, dp[v]);
		}
	}
	
	cout << ans << endl;
	
}

Measured memory_bytes: 8576
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

int main()
{
    int n, t; cin >> n >> t;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];

    ll ans = 0LL;
    int pre = v[0];
    for (int i = 1; i < n; ++i) {
        ans += min(t, v[i]-v[i-1]);
    }

    ans += t;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

num_balls = [0]*(n+1)
for i in range(n):
    num_balls[a[i]] += 1
num_balls = sorted(num_balls, reverse = True)
# print(num_balls)

print(sum(num_balls[k:]))


Measured memory_bytes: 24748
// 問題の URL を書いておく
// 

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>

using namespace std;

//#define ENABLE_PRINT

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

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

using ll = int64_t;

ll simple(int n, vector<ll>& x, vector<ll>& y)
{
    ll ans = 0;
    for(int i = 0; i < n - 1; ++i)
    {
        for(int j = i + 1; j < n; ++j)
        {
            ans = max(ans, abs(x[j] - x[i]) + abs(y[j] - y[i]));
        }
    }
    return ans;
}

struct Point
{
    ll x;
    ll y;
};

Point f(Point p)
{
    return {p.x - p.y, p.x + p.y};
}

ll optimize(int n, vector<Point>& p)
{
    vector<Point> pp(n);
    rep(i, n)
    {
        pp[i] = f(p[i]);
    }
    ll t;
    {
        ll a = numeric_limits<ll>::min(), b = numeric_limits<ll>::max();
        rep(i, n)
        {
            a = max(a, pp[i].x);
            b = min(b, pp[i].x);
        }
        t = a - b;
    }

    ll t2;
    {
        ll a = numeric_limits<ll>::min(), b = numeric_limits<ll>::max();
        rep(i, n)
        {
            a = max(a, pp[i].y);
            b = min(b, pp[i].y);
        }
        t2 = a - b;
    }
    return max(t, t2);

}

void test()
{
    auto n = rand() % 10 + 2;
    vector<ll> x(n), y(n);
    vector<Point> p(n);
//    const int RM = 1000000000 - 1;
    const int RM = 10;
    rep(i, n)
    {
        x[i] = rand() % (RM) + 1;
        y[i] = rand() % (RM) + 1;
        p[i] = {x[i], y[i]};
    }
    auto sa = simple(n, x, y);
    auto oa = optimize(n, p);
    if(sa != oa)
    {
        printf("%d\n", n);
        rep(i, n)
        {
            printf("%ld %ld\n", x[i], y[i]);
        }

        printf("sa=%lld\n", sa);
        printf("oa=%lld\n", oa);
    }
}

int main(int, const char**)
{
    int n;
    cin >> n;
    vector<ll> x(n), y(n);
    vector<Point> p(n);
    rep(i, n)
    {
        cin >> x[i] >> y[i];
        p[i] = {x[i], y[i]};
    }

    auto os = optimize(n, p);
    cout << os << endl;
//    auto sa = simple(n, x, y);
//    cout << sa << endl;

//    rep(i, 100)
//    {
//        test();
//    }

    return 0;
}


Measured memory_bytes: 12764
#include<bits/stdc++.h>
using namespace std;
int main() {
    int N,x;
    int a[120];
    cin >> N >> x;
    for(int i=0; i<N; i++) {
        cin >> a[i];
    }
    sort(a, a+N);
    int count  = 0;
    int i= 0;
    for(int i=0; i<N; i++){
        x = x - a[i];
        if(x < 0) {
            break;
        }
        count++;
    }
    if(x > 0) {
        count--;
    }
    cout << count << endl;
}

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

#define si static inline
#define gcu getchar_unlocked
si int in() {
	int c, n = 0;
	bool minus = false;
	if ((c = gcu()) == '-') minus = true;
	else ungetc(c, stdin);
	while ((c = gcu()) >= '0' && c <= '9') n = 10 * n + (c - '0');
	return minus ? -n : n; }
#define pcu putchar_unlocked
#define svo si void out
svo(int n) {
	static char buf[20];
	char *p = buf;
	bool minus = false;
	if(n < 0) minus = true, n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	if (minus) *p++ = '-';
	while (p != buf) pcu(*--p); }
svo(const char *s){while(*s)pcu(*s++);}
svo(char c){pcu(c);}
template <typename head, typename... tail>
svo(head&& h, tail&&... t){out(h);out(move(t)...);}

typedef vector<int> v;
typedef v::iterator vi;
bool first = true;
void walk(vi &b, vi l, vi r)
{
	vi c = find(l, r, *b);
	if (c == r)
		return;
	b++;
	walk(b, l, c);
	walk(b, c + 1, r);
	out(first ? first = false, "" : " ", *c);
}

int main()
{
	int n = in();
	v p(n), i(n);
	for (int &x: p) x = in();
	for (int &x: i) x = in();

	vi b = p.begin();
	walk(b, i.begin(), i.end());
	out('\n');
}



Measured memory_bytes: 2632
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    string s1,s2;
    int cont=0;
    cin>>s1>>s2;
    for(int i=0;i<s1.size();i++){
        if(s1[i]!=s2[i]){
            cont++;
        }
    }
    cout<<cont<<endl;

    return 0;

}

Measured memory_bytes: 3904
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>
#define LL long long
#define add_edge(u,v) nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
char ch;bool fs;void re(int& x)
{
	while(ch=getchar(),ch<33);
	if(ch=='-')fs=1,x=0;else fs=0,x=ch-48;
	while(ch=getchar(),ch>33)x=x*10+ch-48;
	if(fs)x=-x;	
}
using namespace std;
int n,a,b;
int main()
{
	re(n),re(a),re(b);
	printf("%d\n",min(n*a,b));
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

int main(){
  int h,w;
  cin >> h >> w;
  int k;
  cin >> k;
  vector<vector<char>> maze(h,vector<char>(w));
  rep(i,h) rep(j,w) cin >> maze[i][j];
  int ans = 0;
  rep(i,pow(2,h)){//縦を全探索
    rep(j,pow(2,w)){//横を全探索
      int tmp = 0;//各ケースのtemp
      rep(p,h){//縦を操作
        bool bit = (i>>p)&1;
        if (bit) continue;
        rep(q,w){//横を操作
          bit = (j>>q)&1;
          if (bit) continue;
          if (maze[p][q] == '#') tmp++;
        }//w
      }//p
      if (tmp == k) ans++;
    }//j
  }//i
  cout << ans << endl;
}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
//ll ncr(ll n,ll r){ll ans=1;r=min(r,n-r);for (int i=1;i<=r;i++){ans*=(n-r+i);ans/=i;}return ans;}
using namespace std;
//using namespace __gnu_pbds;
#define pb push_back
#define eb emplace_back
#define mp(x,y) make_pair(x,y)
#define mod 1000000007
double PI=3.1415926535897932384626;
//template<typename T> T power(T x,T y,ll m=mod){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}
#define bip(n) __builtin_popcount(n)//no of ones bit in binary!!
#define bictz(n) __builtin_ctz(n)//no of trailing zeroes in binary!!
#define biclz(n) __builtin_clz(n)//no of leading zeroes in binary!!
#define bffs(n) __builtin_ffs(n)//index of first one bit!!
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;

//#define fi1 ifstream fin("input.txt")
//#define of1 ofstream fout("output.txt")
//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ost;

#define fi first
#define se second

int connected[105][105]={0};

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
	int n;
	cin>>n;
	if(n&1)
	{
		int n1=n-1;
		for(int i=1;i<=n1/2;i++)
		{
			connected[i][n1-i+1]=1;
			connected[n1-i+1][i]=1;
		}
	}
	else
	{
		for(int i=1;i<=n/2;i++)
		{
			connected[i][n-i+1]=1;
			connected[n-i+1][i]=1;
		}
	}
	vii ans;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(connected[i][j]==0)
			{
				ans.eb(mp(i,j));
			}
		}
	}
	cout<< ans.size() <<endl;
	for(auto &x:ans)
	{
		cout<< x.first<<" "<<x.second <<endl;
	}
    return 0;
}

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

int main(){
  string s;
  cin >> s;
  int n = s.size();
  ll ans = 0;
  for(int i = 0; i < (1<<(n-1)); i++){
    ll temp = 0;
    for(int j = 0; j < n-1; j++){
      temp *= 10;
      temp += s[j] - '0';
      if(i & (1<<j)){
        ans += temp;
        temp = 0;
      }
    }
    temp *= 10;
    temp += s.back() - '0';
    ans += temp;
  }
  cout << ans << endl;
  return 0;
}

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

int ft_sqrt(int nb)
{
	int i = 1;
	int count = 0;
	while (i <= nb)
	{
		if (i % 2 == 1)
		{
			nb -= i;
			count++;
		}
		i++;
	}
	if (nb == 0)
		return 1;
	return 0;
}


int main(void)
{
	int N,D;
	scanf("%d%d",&N,&D);
	int x[N][D];
	int i = 0;
	int j;
	while (i < N)
	{
		j = 0;
		while (j < D)
			scanf("%d", &x[i][j++]);
		i++;
	}
	i = 0;
	int count = 0;
	int sum;
	int k,l;
	int y,z;
	while (i < N)
	{
		j = i + 1;
		while (j < N)
		{
			sum = 0;
			k = 0;
			while (k < D)
			{
				sum += abs(x[i][k] - x[j][k]) * abs(x[i][k] - x[j][k]);
				k++;
			}
			if (ft_sqrt(sum))
				count++;
			j++;
		}
		i++;
	}
	printf("%d\n", count);
	return 0;
}

Measured memory_bytes: 128
@n = gets.to_i
@cs, @ss, @fs = [], [], []
(@n-1).times do |i|
    c, s, f = gets.strip.split.map(&:to_i)
    @cs << c
    @ss << s
    @fs << f
end

# 今の時刻と今いる駅から、次の駅の到着時刻を返す
def next_train now, where
    return @ss[where] + @cs[where] if now <= @ss[where]
    return now + @cs[where] if now % @fs[where] == 0
    now + (@fs[where] - now % @fs[where]) + @cs[where]
end

# i からスタートした人がゴールにつくのにかかる時間
def solve_for i
    (i..@n-2).inject(0) { |acc, j| next_train(acc, j) }
end

@n.times do |i|
    puts solve_for i
end

Measured memory_bytes: 1788
h, w = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
grid = []
for i, num in enumerate(A, 1):
    grid += [i]*num


def split_list(l, n):
    for i in range(0, len(l), n):
        yield l[i:i+n]


ans = list(split_list(grid, w))
for i in range(h):
    if i % 2 == 0:
        print(*ans[i])
    else:
        print(*ans[i][::-1])


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int T[200005][30];

int main()
{
    string S;
    cin >> S;
    REP(i, S.length())
    {
        T[i][(int)(S[i] - 'a')]++;
    }
    FOR(i, S.length(), 1)
    {
        REP(j, 30)
        {
            T[i][j] += T[i - 1][j];
        }
    }

    ll sum = 1;
    REP(i, S.length())
    {
        int t = (int)(S[i] - 'a');
        sum += (S.length() - 1 - i) - (T[S.length() - 1][t] - T[i][t]);
    }
    cout << sum << endl;
    return 0;
}

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

using namespace std;

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

    if ( (B - A) % 2 == 0 ) {
        cout << (B - A) / 2 << endl;
    } else {
		long long res = min(A - 1, N - B);
		res += (1 + (B - A - 1)/2);
        cout << res << endl;
    }
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
a.append(0)
a.insert(0,0)
total=0
ans=[]
for i in range(len(a)-1):
    total+=abs(a[i+1]-a[i])
for i in range(n):
    ans.append(total-(abs(a[i+1]-a[i])+abs(a[i+2]-a[i+1]))+abs(a[i+2]-a[i]))
for j in ans:
    print(j)

Measured memory_bytes: 14300
//#define _GLIBCXX_DEBUG
#include "bits/stdc++.h"

using namespace std;

//------------------------------- Type Names -------------------------------//

using i64 = int_fast64_t;

using seika = string;
//{akari : 1D, yukari : 2D, maki : 3D} vector
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
template <class tsurumaki>
using maki = akari<yukari<tsurumaki>>;
//{akane : ascending order, aoi : decending order} priority queue
template <class kotonoha>
using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;
template <class kotonoha>
using aoi = priority_queue<kotonoha>;

//------------------------------- Libraries ---------------------------------//

//------------------------------- Dubug Functions ---------------------------//
inline void print()
{
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest)
{
    cout << first << ' ';
    print(rest...);
}
//------------------------------- Solver ------------------------------------//

void solve()
{
    int s = 0;
    for (int i = 0; i < 3; i++)
    {
        int a;
        cin >> a;
        s += a;
    }
    cout << (s <= 21 ? "win" : "bust") << endl;
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef vector<int> vec1;
typedef vector<string> vec2;
typedef vector<double> vec3;

int main() {
  
  int r;
  cin >> r;
  double a = 2 * 3.14 * r;
  cout << a << endl;
}

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


vector<int> A;


void input() {
    A = vector<int>(3);
    rep(i, 3) cin >> A[i];
}


int main() {
    input();
    sort(A.begin(), A.end());
    int ans = A[2] - A[0];
    cout << ans << endl;
}


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

ans=0
for i in range(N):
    ans += min(A[i],B[i])
    if B[i]>A[i]:
        sarani = min(A[i+1],B[i]-A[i])
        A[i+1] -= sarani
        ans += sarani
print(ans)

Measured memory_bytes: 18624
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}



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

    vector<pair<pair<int,int>,pair<int,int>>> v; //time,distance,ID,head or tail
    rep(i,n){
        int s,t,x;
        cin >> s >> t >> x;
        s = max(0,s-x);
        t = max(0,t-x);
        pair<pair<int,int>,pair<int,int>> p;
        p.first.first = s;
        p.first.second = x;
        p.second.first = i;
        p.second.second = 0;
        v.push_back(p);
        p.first.first = t;
        p.second.second = 1;
        v.push_back(p);
    }
    sort(v.begin(),v.end());

    vector<pair<int,int>> ans; //time,distance

    priority_queue<pair<int,int>> que; //dist,ID
    int flag[n] = {}; //if_use_ID

    rep(i,n*2){
        if(v[i].second.second==0){
            que.push(pair<int,int>(-v[i].first.second,v[i].second.first));
            int dist = -que.top().first;
            ans.push_back(pair<int,int>(v[i].first.first,dist));
        }else{
            flag[v[i].second.first] = 1;
            while(que.size()>0){
                if(flag[que.top().second]==1){
                    que.pop();
                }else{
                    break;
                }
            }
            if(que.size()==0){
                ans.push_back(pair<int,int>(v[i].first.first,-1));
            }else{
                ans.push_back(pair<int,int>(v[i].first.first,-que.top().first));
            }
        }
    }

    int dd[q];
    rep(i,q)cin>>dd[i];

    rep(i,q){
        int d; d = dd[i];
        if(d<ans[0].first){
            cout << "-1" << endl;
        }else if(ans[n*2-1].first<=d){
            cout << "-1" << endl;
        }else{
            int l = 0;
            int r = n*2-1;
            while(true){
                int mid = (l+r)/2;
                if(d<ans[mid].first){
                    r = mid;
                }else{
                    l = mid;
                }
                if(r-l<=1){
                    cout << ans[l].second << endl;
                    break;
                }
            }
        }
    }

    return 0;
}
 
 


Measured memory_bytes: 18664
#include <bits/stdc++.h>
using namespace std;
long long l[8];
int N,A,B,C;
const int INF = 1e9+7;
int dfs(int num,int a,int b,int c,int sum){
	if(num==N){
		if(a==0||b==0||c==0)return INF;
		else return abs(A-a)+abs(B-b)+abs(C-c)+sum*10 - 30;
	}
	int cost1=dfs(num+1,a+l[num],b,c,sum+1);
	int cost2=dfs(num+1,a,b+l[num],c,sum+1);
	int cost3=dfs(num+1,a,b,c+l[num],sum+1);
	int cost4=dfs(num+1,a,b,c,sum);
		return min({cost1,cost2,cost3,cost4});
}

int main(void){
	
	cin >> N >> A >> B >> C;
	for(int i=0;i<N;i++)cin >> l[i];
	cout << dfs(0,0,0,0,0) << endl;
}

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

using namespace std;

typedef pair<int,int> pi;

#define p 1e9+7

int main()
{
    int n;
    cin>>n;
    int N = pow(2,n);
    vector<vector<int> > cpt(n,vector<int>(n,0));
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin>>cpt[i][j];

    vector<int> ans(pow(2,n),0);

    ans[0]=1;
    for(int k=1; k<=n; k++)
    {
        int bitmask=pow(2,k)-1;
        while(bitmask<N)
        {
            for(int j=0; j<n; j++)
            {
                if(! ((1<<j) & bitmask))continue;
                int b2 = bitmask ^ (1<<j);
                if(cpt[k-1][j])
                {
                    ans[bitmask] += ans[b2];
                    if(ans[bitmask]>=p)ans[bitmask]-=p;
                }
            }
            
            // cout<<bitmask<<endl;
            int a = bitmask & (-bitmask);
            int c = bitmask + a;
            bitmask = c + (bitmask^c)/a/4;
        }
    }

    cout<<ans[pow(2,n)-1];
    return 0;
}

Measured memory_bytes: 8448
#include<iostream>
using namespace std;
int main(void)
{
    int n;
    int min,max;
    long long int sum=0;
    int num;
    cin>>n;
    cin>>num;
    min=max=num;
    sum+=num;
    for(int i=1;i<n;++i)
    {
        cin>>num;
        if(min>num)
        {
            min=num;
        }
        if(max<num)
        {
            max=num;
        }
        sum+=num;
    }
    cout<<min<<" "<<max<<" "<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first 
#define se second 
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
 

int main(){
 ll n,m ;
 cin>> n>>m ;
 vector<ll> A(n) ; rep(i,n) cin>>A[i] ;
 ll sum= 0 ; rep(i,n) sum+= A[i] ;
 priority_queue<ll>  hiki ;
 rep(i,n){
 hiki.push(A[i]) ;
 }
 ll ans=0 ;
 rep(i,m){
  ll x= hiki.top() ;
  hiki.pop() ;
  ans+= x-(x/2) ;
  hiki.push(x/2) ;
  
 }
 
  cout<<sum-ans<<endl ;
  return 0;
  }

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

int main()
{
    int n;
    cin >> n;
    int a[102];
    int s = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        s += a[i];
    }
    int d = 10000000;
    int ans = -1;
    for(int i = 0; i < n; i++){
        if(abs(s - a[i] * n) < d){
            d = abs(s - a[i] * n);
            ans = i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
typedef long long ll;


int main()
{
  ll N;
  cin >> N;
  vector<ll> A(N);
  for (ll i = 0; i < N; ++i)
  {
    cin >> A.at(i);
  }
  vector<ll> dp(N + 1, INF);// dp[連続数] = 最大値
  dp.at(0) = -1;
  for (ll i = 0; i < N; ++i)
  {
    ll index = lower_bound(dp.begin(), dp.end(), A.at(i)) - dp.begin();
    dp.at(index) = A.at(i);
    // for (ll j = 0; j < N; ++j)
    // {
    //   if (dp.at(j) < A.at(i))
    //   {
    //     dp.at(j + 1) = min(A.at(i), dp.at(j + 1));
    //   }
    // }
    // for (ll j = 0; j < N; ++j)
    // {
    //   dp.at(i + 1).at(j) = min(dp.at(i).at(j), dp.at(i + 1).at(j));
    // }
  }
  ll ans = 0;
  for (ll i = 0; i < N + 1; ++i)
  {
    if (dp.at(i) != INF)
    {
      ans = i;
    }
  }
  // for (ll i = 0; i < N + 1; ++i)
  // {
  //   cout << dp.at(i) << endl;
  // }
  cout << ans << endl;
}



Measured memory_bytes: 4412
#include <stdio.h>
typedef long long ll;
int main(void){
  ll n,i,j=0,a[200000];
  scanf("%lld",&n);
  for(i=0;i<n;i++) scanf("%lld",&a[i]);
  for(i=0;i<n;i++) j+=a[i];
  printf("%lld",j-n);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int x;
    cin >> x;
    int t;
    cin >> t;
    if (n % x == 0)
    {
        cout << t * (n / x);
    }
    else
    {
        cout << t * ((n / x) + 1);
    }
}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <sstream>
#include <istream>

using namespace std;

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

int main(){
	int num[26];

	for(int i=0;i<26;i++) num[i] = 0;
	string s;
	cin >> s;
	for(int i=0;i<4;i++) num[s[i]-'A']++;
	int n = 0;
	for(int i=0;i<26;i++) if(num[i]==2)n++;
	if(n==2){
		cout << "Yes" << endl;
	}else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

int main(){
  long l,n;
  cin>>l>>n;
  vector<long> v(n);
  rep(i,n) cin>>v[i];

  if(n==1){
    cout << max(v[0], l-v[0]) << endl;
    return 0;
  } else if(n==2){
    long ans = max({2*v[0] + l-v[1], 2*(l-v[1]) + v[0], l-v[0], v[1]});
    cout << ans << endl;
    return 0;
  }

  long ans = max(v.back(), l - v[0]);

  rep(_,2){
    vector<long> accl(n+2,0), accr(n+2,0);
    rep(i,n) accl[i+1] = accl[i] + v[i];
    for(int i=n-1; i>=0; i--) accr[i] = accr[i+1] + l - v[i];

    // dbg(accl, accr);
    rep(i,1,n/2 + 1){
      ans = max<long>(ans, accl[i] + accl[i-1] +  2*(accr[i] - accr[i+i]));
      ans = max<long>(ans, 2*accl[i] + accr[i] + accr[i+1] - 2*accr[i+i+1]);
    }
    reverse(all(v));
    rep(i,n) v[i] = l - v[i];
  }

  cout << ans << endl;

  return 0;
}


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

int main(){
  
  int N;
  cin >> N;
  int A[N],B[N-1];
  
  for (int i = 0; i < N+1; i++){
    cin >> A[i];
  }
  
  for (int i = 0; i < N; i++){
    cin >> B[i];
  }
  
  long long counter = 0;
  
  for (int i = 0; i < N; i++){
    if (B[i] <= A[i]){
      counter += B[i];
    }else if(B[i] <= A[i] + A[i+1]){
      counter += B[i];
      A[i+1] -= B[i] - A[i];
    }else{
      counter += A[i] + A[i+1];
      A[i+1] = 0;
    }
  }
  
  cout << counter << endl;
}

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

using namespace std;

int l;
long long x[200005][5];
long long ta;

int main() {
	scanf("%d", &l);
	for (int i = 0; i < l; i++) {
		scanf("%lld", &ta);
		x[i + 1][0] = x[i][0] + ta;
		x[i + 1][1] = min(x[i + 1][0], x[i][1] + (ta == 0 ? 2 : (ta & 1)));
		x[i + 1][2] = min(x[i + 1][1], x[i][2] + ((ta & 1) ^ 1));
		x[i + 1][3] = min(x[i + 1][2], x[i][3] + (ta == 0 ? 2 : (ta & 1)));
		x[i + 1][4] = min(x[i + 1][3], x[i][4] + ta);
	}
	printf("%lld\n", x[l][4]);
	return 0;
}

Measured memory_bytes: 8064
#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
  #define all(v) v.begin(),v.end()
  #define rep(i,a,b) for(int i = a; i <=b; i++)
  #define f first
  #define s second
  #define PB push_back
  #define MP make_pair
  #pragma comment(linker, "/STACK:2000000")
  #pragma comment(linker, "/HEAP:2000000")
  #define db long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
  #define MOD 1000000007
  int32_t main()
  {        
    IOS
    int a,b,c;
    cin>>a>>b>>c;
    int d=min(c,a-b);
    cout<<c-d;
    return 0;
} 

Measured memory_bytes: 256
import sys
import math

#https://atcoder.jp/contests/agc008/submissions/15248942
sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

S = input()

ans = 0
for c in S:
    if c == '+':
        ans += 1
    else:
        ans -= 1

print(ans)

Measured memory_bytes: 8980
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const int INF = 1e8;

int main(void){
    int n;
    cin >> n;
    VI x(n), y(n);
    vector<char> d(n);
    REP(i,n){
        x[i] = in();
        y[i] = in();
        cin >> d[i];
    }
    map<int, vector<pair<int, char>>> x2y, y2x, p2m, m2p;
    REP(i,n){
        x2y[x[i]].emplace_back(y[i], d[i]);
        y2x[y[i]].emplace_back(x[i], d[i]);
        p2m[x[i] + y[i]].emplace_back(y[i] - x[i], d[i]);
        m2p[y[i] - x[i]].emplace_back(x[i] + y[i], d[i]);
    }
    int ans = INF;
    for (auto tmp : x2y){
        sort(ALL(tmp.second));
        int u = -INF;
        for (auto p : tmp.second){
            if (p.second == 'U') u = p.first;
            else if (p.second == 'D') chmin(ans, 5 * (p.first - u));
        }
    }
    for (auto tmp : y2x){
        sort(ALL(tmp.second));
        int r = -INF;
        for (auto p : tmp.second){
            if (p.second == 'R') r = p.first;
            else if (p.second == 'L') chmin(ans, 5 * (p.first - r));
        }
    }
    for (auto tmp : p2m){
        sort(ALL(tmp.second));
        int u = -INF, l = -INF;
        for (auto p : tmp.second){
            if (p.second == 'U') u = p.first;
            else if (p.second == 'L') l = p.first;
            else if (p.second == 'R') chmin(ans, 5 * (p.first - u));
            else if (p.second == 'D') chmin(ans, 5 * (p.first - l));
        }
    }
    for (auto tmp : m2p){
        sort(ALL(tmp.second));
        int u = -INF, r = -INF;
        for (auto p : tmp.second){
            if (p.second == 'U') u = p.first;
            else if (p.second == 'R') r = p.first;
            else if (p.second == 'L') chmin(ans, 5 * (p.first - u));
            else if (p.second == 'D') chmin(ans, 5 * (p.first - r));
        }
    }
    if (ans == INF) cout << "SAFE" << endl;
    else cout << ans << endl;
    return 0;
}


Measured memory_bytes: 73176
def INPUT():return list(int(i) for i in input().split())
#====================
n=int(input())
ans=""
for i in range(1,14):
    if n<=26**i:
        n-=1
        for j in range(i):
            ans+=chr(ord('a')+n%26)
            n//=26
        break
    else:
        n-=26**i
print(ans[::-1])


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

int a[110], b[110];

int main() {
	int n, m, x, y; cin >> n >> m >> x >> y;
	for (int i = 0; i < n; i ++) cin >> a[i];
	for (int i = 0; i < m; i ++) cin >> b[i];
	bool flag = false;
	for (int z = x+1; z <= y; z ++) {
		bool ok = true;
		for (int i = 0; i < n; i ++) 
			if (a[i] >= z) { ok = false; break; }
		for (int i = 0; i < m; i ++)
			if (b[i] < z) { ok = false; break; }
		if (ok) { flag = true; break; }
	}
	if (flag) cout << "No War\n";
	else cout << "War\n";
	
	return 0;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF 9223372036854775807

#define MAX_N 1000

map<char,int> prio;
string s;

ll expr(int l,int r){
	//dbg(s.substr(l,r-l));
	// num
	bool isnum=true;
	repl(i,l,r){
		if(!isdigit(s[i]))isnum=false;
	}
	if(isnum)return stoll(s.substr(l,r-l));

	// (expr)
	ll lev;
	if(s[l]=='('){
		lev=0;
		bool isk=true;
		repl(i,l,r){
			if(s[i]=='(')lev++;
			if(s[i]==')')lev--;
			if(i!=r-1&&lev==0)isk=false;
		}
		if(isk)return expr(l+1,r-1);
	}

	// expr op expr	
	rep(j,3){
		lev=0;
		for(int i=r-1;i>=l;i--){
			if(s[i]=='(')lev++;
			if(s[i]==')')lev--;
			if(lev==0&&prio.count(s[i])&&prio[s[i]]==j){
				ull resa=expr(l,i),resb=expr(i+1,r);
				if(s[i]=='+'){
					return resa+resb;
				}else if(s[i]=='-'){
					return resa-resb;
				}else{
					return resa*resb;
				}
			}
		}
	}
	return 0;
}

int main(){
	cin.sync_with_stdio(false);
	cin>>s;
	ll res=-INF;
	prio['+']=prio['-']=prio['*']=0;
	rep(i,27){
		prio['+']=i/9;
		prio['-']=i%9/3;
		prio['*']=i%3;
		maxch(res,expr(0,s.length()));
		//rep(j,3)dbg(prio[j]);
		//dbg(res);
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 3216
import math
k=int(input())
ans=0
for a in range(1,k+1):
  for b in range(a,k+1):
    for c in range(b,k+1):
      ans+=math.gcd(math.gcd(a,b),c)*(1 if a==b==c else (3 if a==b or b==c else 6))
print(ans)

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

int main(){

    int n;
    cin >> n;
    vector<pair<int, int> > odd((int)(1e5) + 1);
    vector<pair<int, int> > even((int)(1e5) + 1);
    for(int i=0; i<=1e5; i++){
        odd[i].first = 0;
        odd[i].second = i;
        even[i].first = 0;
        even[i].second = i;
    }

    for(int i=0; i<n; i++){
        int newnum;
        cin >> newnum;
        if(i % 2 == 0){
            odd[newnum].first ++;
        }else{
            even[newnum].first ++;
        }
    }


    sort(odd.begin(), odd.end());
    sort(even.begin(), even.end());

    
    pair<int, int> most_freq_odd = odd[(int)(1e5)];
    pair<int, int> most_freq_even = even[(int)(1e5)];
    int ans;

    if(most_freq_odd.second != most_freq_even.second){
        
        ans = n - most_freq_even.first - most_freq_odd.first;
    }else{
        int ans1 = n - most_freq_even.first - odd[(int)(1e5)-1].first;
        int ans2 = n - most_freq_odd.first - even[(int)(1e5)-1].first;
        ans = min(ans1, ans2);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1920
#include<stdio.h>
/*
int handan(int x,int k){
  if(0<x && x<k){
  if(x<(k/2)){
    return (2*x);
  }
  else
    return (2*(k-x));
  }
  else return 0;
}
*/
    

int main(void){
  int n,k;
  int x;
  //int handan(x,k);
    int sum = 0;

  
  scanf("%d", &n);
  scanf("%d", &k);
  for(int i=0;i<n;i++){
  	scanf("%d", &x);
    if(x<(k-x)){
    sum += (2*x);
    }
    else
    sum += (2*(k-x));
    
    //handan(x,k);
    //sum += handan(x,k);
  }
 /*
  for(int i=0;i<n;i++){
    //handan(x,k);
    if(x<(k/2)){
    sum += (2*x);
    }
    else
    sum += (2*(k-x));
  
    //sum += handan(x,k);
  }
  */
  
  printf("%d", sum);
  return 0;
}


Measured memory_bytes: 1728
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

vector<int> G[100000];
int N,M;
int color[100000]={0};

bool dfs(int v,int c){
    color[v]=c;
    for(int i=0;i<G[v].size();i++){
        if(color[G[v][i]]==c) return false;
        if(color[G[v][i]]==0&&!dfs(G[v][i],-c)) return false;
    }
    return true;
}

int main(){
    int N,M;
    cin >> N >> M;
    for(int i=0;i<M;i++){
        int v,u;
        cin >> v >> u;
        G[v].push_back(u);
        G[u].push_back(v);
    }
    if(!dfs(1,1)){
        cout << (LL)N*(N-1)/2-M << endl;
        return 0;
    }
    int countR=0,countW=0;
    for(int i=1;i<=N;i++){
        if(color[i]==1) countR++;
        else countW++;
    }
    cout << (LL)countR*countW-M << endl;
    return 0;
}

Measured memory_bytes: 6528
'use strict';
function main(input) {
  input = input.split("\n");
  const a = 'abcdefghijklmnopqrstuvwxyz';
  const aIndex = a.indexOf(input[0]);
  
  console.log(a[aIndex + 1]);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main()
{
	int a, b;
	cin >> a >> b;
	if( a == 1 ) a = 14;
	if( b == 1 ) b = 14;

	string ans;
	if( a > b ) {
		ans = "Alice";
	}
	if( a < b ) {
		ans = "Bob";
	}
	if( a == b ) {
		ans = "Draw";
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
/*
for (int i = 0; i < N; ++i){}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<int,int> point;
#define rep(i,n) for(i,0,n)

// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
 

int main() {
	// 入力
	ll a[3];
	cin >> a[0] >> a[1] >> a[2];
 
	// 解法
	sort(a, a + 3, greater<int>());  // a[0:N] を大きい順にソート
	cout << a[0]*10+a[1]+a[2] << endl;
	
}
 


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int x,y;
    while(1){
        scanf("%d %d",&x,&y);
        if(x==0 && y==0){
            break;
        }else if(y<x){
            int tmp;
            tmp=x;
            x=y;
            y=tmp;
        }
        printf("%d %d\n",x,y);
        }
    }



Measured memory_bytes: 2032
import numpy as np
hi = np.zeros((5000,60),np.int64)
hi[0,0]=1
n,a = map(int, input().split())
li = [int(it) for it in input().split()]
for i in li:
    hi_ = hi.copy()
    hi[i:-1,1:]+=hi_[:-1-i,:-1]
s = 0
for i in range(n):
  s+=hi[(i+1)*a,i+1]
print (s)

Measured memory_bytes: 19684
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
    static final int INF = 1000000000;         
    static int cmps = 0;
    
    public static void main(String[] args) throws Exception {                
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] s = new int[n];
        for (int i = 0; i < n; ++i) s[i] = input.nextInt();
        mergeSort(s, 0, n);
        System.out.print(s[0]);
        for (int i = 1; i < n; ++i) System.out.print(" " + s[i]);
        System.out.println("");
        System.out.println(cmps);
    }              
    
    static void mergeSort(int[] A, int left, int right) {
        if (left + 1 < right) {
            int mid = (left + right) / 2;
            mergeSort(A, left, mid);
            mergeSort(A, mid, right);
            merge(A, left, mid, right);
        }
    }
    
    static void merge(int[] A, int left, int mid, int right) {
        int n1 = mid - left;
        int n2 = right - mid;
        int[] L = new int[n1 + 1];
        int[] R = new int[n2 + 1];
        for (int i = 0; i < n1; ++i) L[i] = A[left + i];
        for (int i = 0; i < n2; ++i) R[i] = A[mid + i];
        L[n1] = R[n2] = INF;
        int i, k;
        i = k = 0;
        for (int t = left; t < right; ++t) {
            if (L[i] < R[k]) {
                A[t] = L[i++];
                ++cmps;
            } else {
                A[t] = R[k++];
                ++cmps;
            }
        }
    }
}

Measured memory_bytes: 166260
// #pragma GCC optimize("unroll-loops", "omit-frame-pointer", "inline")
// #pragma GCC option("arch=native", "tune=native", "no-zero-upper")
// #pragma GCC
// target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("tree-vectorize","openmp","predictive-commoning")
// #pragma GCC option("D_GLIBCXX_PARALLEL","openmp")

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
// #define int long long
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000               // 2e9
#define LLINF 2000000000000000000ll  // 2e18 (llmax:9e18)
#define fi first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define dmp(x) cerr << #x << ": " << x << endl;

template <class T>
void chmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T &a, const T &b) {
  if (a < b) a = b;
}

template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
vector<T> vect(int len, T elem) {
  return vector<T>(len, elem);
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.fi << ',' << p.sec;
  return os;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.fi >> p.sec;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i];
    if (i + 1 < vec.size()) os << ' ';
  }
  return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) is >> vec[i];
  return is;
}
void fastio() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
}

#define endl "\n"

void solve() {
  ll x, k, d;
  cin >> x >> k >> d;

  ll m = 0ll;
  if (k & 1)
    m = (x + d) % (2 * d);
  else
    m = x % (2 * d);
  m = (m + 2 * d) % (2 * d);

  ll target = m;
  if (abs(m) > abs(m - 2 * d)) target = m - 2 * d;
  if (abs(target - x) / d > k) {
    if (x > 0)
      cout << x - k * d << endl;
    else
      cout << abs(x + k * d) << endl;
    return;
  }
  cout << abs(target) << endl;
  return;
}

signed main() {
  fastio();
  solve();
  // int t; cin >> t; while(t--)solve();

  // int t; cin >> t;
  // for(int i=1;i<=t;i++){
  //   cout << "Case #" << i << ": ";
  //   solve();
  // }
  return 0;
}


Measured memory_bytes: 3648
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

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

#define io ios_base::sync_with_stdio(false)
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vll vector<long long>
#define pb push_back
#define mod 998244353
#define pii pair<int, int>
#define PI 2*acos(0.0)

int main()
{
    io;
    int r;
    cin>>r;
    double ans = 2.0 * PI * r;
    printf("%.6f", ans);
    return 0;
}


Measured memory_bytes: 3780
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: u16 = read(&mut stdin_lock, &mut buf, b'\n');
    let ans = if n <= 999 { "ABC" } else { "ABD" };
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cassert>
#include <complex>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ctime>
#include <cctype>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <memory.h>
using namespace std;
typedef long long ll;
#define mp make_pair
ll n;
string ans;
int main(){
	cin>>n;
	while(n){
		if(n<=26){
			ans+='a'+n-1;
			break;
		}
		n-=26;
		ans+=((n-1)%26)+'a';
		n+=25;
		n/=26;
	}
	for(int i=ans.size()-1;i>=0;i--){
		cout<<ans[i];
	}
	return 0;
}


Measured memory_bytes: 3636
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <string>
#include <map>
#include <set>

using namespace std;


char g[505][505];

int main() {
	int N; scanf("%d", &N);
	bool flag = true;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			scanf(" %c", &g[i][j]);
			if (g[i][j] == '#')
				flag = false;
		}
	}
	if (flag) {
		cout << -1 << endl; return 0;
	}
	int ans = N + N - 1;
	for (int i = 0; i < N; ++i) {
		int cur = 0;
		for (int j = 0; j < N; ++j)
			if (g[i][j] == '.') ++cur;
		int used = 1;
		for (int j = 0; j < N; ++j)
			if (g[j][i] == '#') used = 0;
		cur += used;
		if (cur < ans) ans = cur;
	}
	for (int i = 0; i < N; ++i) {
		int cnt = 0;
		for (int j = 0; j < N; ++j)
			if (g[j][i] == '.') cnt = 1;
		ans += cnt;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>

int main(void){
        int n, a=0, b=0;;
        scanf("%d", &n);

        for(int i=0; i<n; i++){
                char s[101], t[101];
                scanf("%s %s", s, t);

                for(int j=0; j<101; j++){
                        if(s[j]=='\0'){
                                if(t[j]=='\0'){
                                        a++;
                                        b++;
                                }else b += 3;
                        }else if(t[j]=='\0') a += 3;
                        else{
                                if(s[j]==t[j]) continue;
                                if(s[j]>t[j]) a += 3;
                                else b += 3;
                        }
                        break;
                }
        }
        printf("%d %d\n", a, b);
        return 0;
}


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

using namespace std;

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

  int a[1000];
  for(int i=0; i< 1000; ++i){
    a[i] = -1;
  }

  bool check = true;

  for(int i=0;i <s.size(); ++i){
    if(a[s[i]] > 0){
      cout << "no" << endl;
      check = false;
      break;
    }
    a[s[i]] = 1;
  }

  if(check){
    cout << "yes" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

xs = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    p = p-1
    xs[p] += x

#print(xs)
from collections import deque
s = deque()
s.append(0)
visit = [-1]*n
visit[0] = 0
while s:
    x = s.pop()
    for new_x in g[x]:
        if visit[new_x] == -1:
            visit[new_x] = 0
            xs[new_x] += xs[x]
            s.append(new_x)
print(*xs)


Measured memory_bytes: 106132
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
    cin>>a[i];
    vector<int>dp(n,INT_MAX);
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<=i+k;j++)
        {
            dp[j]=min(dp[j],dp[i]+abs(a[j]-a[i]));
        }
    }
    cout<<dp[n-1];
}


Measured memory_bytes: 4032