akhauriyash/Code-Regression huggingface dataset:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
A = sorted(A,key=lambda x:x[1])
t = 0
for i in range(N):
    t += A[i][0]
    if t > A[i][1]:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 55264
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N,M; cin >> N >> M;
    int ans = -1;
    vector<int> s(M);
    vector<char> c(M);
    for (int i=0;i<M;i++) cin >> s[i] >> c[i];
    for (int i = (N==1) ? 0 : pow(10, N-1);i<pow(10,N);i++){
        string x = to_string(i);
        bool can = true;
        for (int j=0;j<M;j++){
            if (x[s[j]-1]!=c[j]) can = false;
        }
        if (can) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
 int n,m=0;
  cin >> n;
 vector<int> v(n);
 for (int i=0;i<n;i++)
   cin >> v.at(i);
 sort(v.begin(),v.end());
 reverse(v.begin(),v.end());
 for(int i=0;i<n;i+=2)
  m +=v.at(i);
 for(int i=1;i<n;i+=2)
  m -=v.at(i);
 cout << m << endl;
}

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


def main():
    """Function."""
    a = int(input())
    b = int(input())
    c = int(input())
    d = int(input())

    train, bus = 0, 0
    if a > b:
        train = b
    else:
        train = a

    if c > d:
        bus = d
    else:
        bus = c

    print(train + bus)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int abs(int x) {
    return x<0? -x: x;
}

int main(int argc, char const *argv[])
{
    int n; cin >> n;

    int t=0, x=0, y=0, ti, xi, yi, d;
    for(int i=0;i<n;++i) {
        cin >> ti >> xi >> yi;
        d = (ti-t) - abs(x-xi) - abs(y-yi);
        if(d<0 || (d&1)) {
            cout << "No" << endl;
            return 0;
        }
        t=ti;x=xi;y=yi;
    }
    cout << "Yes" << endl;
    return 0;
}


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

struct node{
    long int father;
    long int points;
};

node tree[MAX];

int main(){
    long int n, q, i, a, b;
    cin >> n >> q;
    tree[1] = {1, 0};
    for(i = 0; i < n-1; i++){
        cin >> a >> b;
        node x = {a, 0};
        tree[b] = x;
    }

    for(i = 0; i < q; i++){
        cin >> a >> b;
        tree[a].points+=b;
    }

    for(i = 2; i <= n; i++){
        tree[i].points+=tree[tree[i].father].points;
    }

    cout << tree[1].points;
    for(i = 2; i <= n; i++){
        cout << " " << tree[i].points;
    }
    cout << endl;
}

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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

template<typename T1,typename T2> using P = pair< T1, T2 >;
using Pii = P<int,int>;
using Pdd = P<double,double>;

template<typename T1,typename T2> using M = map< T1, T2>;
using Mii = M<int, int>;
using Msll = M<string, LL>;

LL factorial(int x,int m=0){
    LL a=1;
    if(m==0){REPD2(i,x,1){a*=i;}}else{REPD2(i,x,1){a=(a*i)%m;}}
    return a;
}

int main(){
    int n,m;
    cin>>n>>m;
    V<Pii> ab(n);
    V<Vi> c(m+1);
    REP(i,n){
        int a,b;
        cin>>a>>b;
        if(a<=m) c[a].pb(b);
    }

    // cout<<endl;
    // REP(i,n){
    //     cout<<ab[i].fi<<" "<<ab[i].se<<endl;
    // }
    // cout<<endl;
    
    priority_queue<int> q;
    LL total = 0;
    REP(i,m){
        REP(j,c[i+1].size()){
            q.push(c[i+1][j]);
        }
        if(!q.empty()){
            total += q.top();
            // cout<<i+1<<" "<<q.top()<<endl;
            q.pop();
        }
    }

    cout<<total<<endl;

    return 0;
}

Measured memory_bytes: 6400
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int array[] = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		bubbleSort(array, n);

	}

	public static void bubbleSort(int array[], int n) {
		int count = 0;
		boolean flag = true;
		while (flag) {
			flag = false;
			for (int j = n - 1; j > 0; j--) {
				if (array[j] < array[j - 1]) {
					swap(array, j, j - 1);
					count++;
					flag = true;
				}
			}
		}
		printArray(array, n);
		System.out.println(count);
	}

	public static void printArray(int array[], int n) {
		for (int i = 0; i < n - 1; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println(array[n - 1]);
	}

	public static void swap(int array[], int a, int b) {
		int tmp = array[a];
		array[a] = array[b];
		array[b] = tmp;
	}

}



Measured memory_bytes: 26260
import java.util.*;
import java.math.*;
import java.lang.String;
import java.lang.System;
import java.lang.reflect.Array;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String A = sc.nextLine();
		String[] Aarr = A.split("");
		String B = sc.nextLine();
		String[] Barr = B.split("");
		String C = sc.nextLine();
		String[] Carr = C.split("");
		String[][] arr = new String[3][];
		arr[0] = Aarr;
		arr[1] = Barr;
		arr[2] = Carr;
		int Acount = 0;
		int Bcount = 0;
		int Ccount = 0;
		String answer = null;
		boolean fin = false;
		int i = 0;
		int j = 0;
		
		while (!fin) {
			if (i == 0) {
				j = Acount;
				Acount++;
				if (Acount > A.length()) {
					fin = true;
					answer = "A";
				}
			} else if (i == 1) {
				j = Bcount;
				Bcount++;
				if (Bcount > B.length()) {
					fin = true;
					answer = "B";
				}
			} else {
				j = Ccount;
				Ccount++;
				if (Ccount > C.length()) {
					fin = true;
					answer = "C";
				}
			}
			if (!fin) {
				if (arr[i][j].equals("a")) {
					i = 0;
				} else if (arr[i][j].equals("b")) {
					i = 1;
				} else {
					i = 2;
				}
			}
		}
		System.out.println(answer);
		
	}
}


Measured memory_bytes: 9684
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
const int maxm=2e3+5;
int d[maxm][maxm];
PI a[maxm];
int n;
bool cmp(PI a,PI b){
    return a.first>b.first;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=0;i<n;i++){
        for(int j=0;i+j<n;j++){//枚举当前状态
            int k=i+j+1;
            d[i][j+1]=max(d[i][j+1],d[i][j]+abs(n-j-a[k].second)*a[k].first);
            d[i+1][j]=max(d[i+1][j],d[i][j]+abs(i+1-a[k].second)*a[k].first);
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        ans=max(ans,d[i][n-i]);
    }
    cout<<ans<<endl;
    return 0;
}
/*
考虑贪心,显然对于权值大的数,选择最左边和最右边贡献大的位置.
但是如果最左边和最右边贡献一样大,就不好判断了,
因为会影响接下来其他数的贡献,
所以这题应该用dp做,

令d[i][j]表示i个元素放在最左边,j个元素放在最右边的最大权值和.
枚举每个状态,向下一个状态转移即可.
*/


Measured memory_bytes: 26288
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			var firstLine = Console.ReadLine().Split(' ').Select(value => int.Parse(value)).ToList();
			var a = firstLine[0];
			var b = firstLine[1];
			var c = firstLine[2];
			
			Console.WriteLine((b - a == c - b) ? "YES" : "NO");
		}
	}
}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int3(n, mm, mmn);
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    
    vvi mmnmm(n+2, vi(n+2, INF));
    mmnmm[0][0] = 0;

    rep(i, n+1) {
        rep(j, n+1) {
            if (i != n && data[i] == j+1) {
                mmnmm[i+1][j+1] = min(mmnmm[i+1][j+1], mmnmm[i][j]);
            }
            if (i != n && data[i] > j) {
                mmnmm[i+1][j] = min(mmnmm[i+1][j], mmnmm[i][j] + mm);
            } else if (i != n) {
                mmnmm[i+1][j] = min(mmnmm[i+1][j], mmnmm[i][j] + mmn);
            }
            mmnmm[i][j+1] = min(mmnmm[i][j+1], mmnmm[i][j]);
            mmnmm[i][j+1] = min(mmnmm[i][j+1], mmnmm[i][j]);
        }
    }
    /*
    rep(i, n+1) {
        rep(j, n+1) {
            cout << mmnmm[i][j] << " ";
        }
        cout << endl;
    }
    */
    cout << mmnmm[n][n] << endl;

    return 0;
}


Measured memory_bytes: 195968
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

#define MAX_N 30

ll memo[MAX_N];
ll res(int n) {
  if(n < 0) return 0;
  if(n == 0) return memo[n] = 1;
  if(n > 0) {
    if(memo[n] != 0) {
      return memo[n];
    }
    else {
      return memo[n] = res(n-3) + res(n-2) + res(n-1);
    }
  }
  return -1;
}

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

  int n;
  while(cin >> n) {
    if( n == 0 ) break;
    ll combo = res(n);
    ll year = (combo / 10) / 365 + 1;
    cout << year << endl;
  }
}

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

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

const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const int int_inf = 100000000;
const double eps = 1e-9;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int h, w;
    cin >> h >> w;

    vector<vector<int>> dist(h, vector<int>(w, int_inf));

    char grid[h][w];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> grid[i][j];
        }
    }

    if (grid[0][0] == '#') dist[0][0] = 1;
    else dist[0][0] = 0;
    
    queue<pair<int, int>> que;
    que.push(make_pair(0, 0));

    while (!que.empty()) {
        auto now = que.front();
        que.pop();
        int now_x, now_y, next_x, next_y, cost;
        now_x = now.first;
        now_y = now.second;

        for (int i = 0; i < 2; i++) {
            next_x = now_x + dx[i];
            next_y = now_y + dy[i];
            if (next_x < 0 or next_x >= h or next_y < 0 or next_y >= w) continue;
            cost = dist[now_x][now_y];
            if (grid[now_x][now_y] == '.' and grid[next_x][next_y] == '#') cost++;
            if (cost < dist[next_x][next_y]) {
                dist[next_x][next_y] = cost;
                que.push(make_pair(next_x, next_y));
            }
        }
    }
    /*
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }*/
    cout << dist[h-1][w-1] << endl;
    
    return 0;
}

Measured memory_bytes: 384
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

string s;

void f(ll n, ll k)
{
    if (n == 0)
    {
        OUT(s);
        return;
    }
    REP1(i, k)
    {
        s.push_back('a' + i - 1);
        f(n - 1, max(i + 1, k));
        s.pop_back();
    }
}

int main()
{
    IN(ll, N);
    f(N, 1);
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
typedef __int128_t Int;
typedef pair<int, int> P;
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T> class DisjointSet {
public:
  vector<T> rank, p;
  int SizeOfCC;
  vector<P> minimum;

  DisjointSet() {}
  DisjointSet(int size) {
    rank.resize(size, 0);
    p.resize(size, 0);
    rep(i, 0, size) makeSet(i);
    SizeOfCC = size;
    minimum.resize(size);
  }
  void makeSet(int x) {
    p[x] = x;
    rank[x] = 0;
  }
  bool same(int x, int y) { return findSet(x) == findSet(y); }
  void unite(int x, int y) {
    if (same(x, y))
      return;
    link(findSet(x), findSet(y));
  }
  void link(int x, int y) {
    SizeOfCC--;
    if (rank[x] > rank[y]) {
      p[y] = x;
    } else {
      p[x] = y;
      if (rank[x] == rank[y]) {
        rank[y]++;
      }
    }
    if (minimum[x].first < minimum[y].first) {
      minimum[y] = minimum[x];
    } else
      minimum[x] = minimum[y];
  }
  int findSet(int x) {
    if (x != p[x]) {
      p[x] = findSet(p[x]); // path compression
    }
    return p[x];
  }
};

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> a(N);
  rep(i, 0, N) { cin >> a[i]; }
  DisjointSet<int> uf(N);
  rep(i, 0, N) { uf.minimum[i] = P(a[i], i); }
  rep(i, 0, M) {
    int x, y;
    cin >> x >> y;
    uf.unite(x, y);
  }
  if (uf.SizeOfCC == 1) {
    cout << 0 << endl;
    return 0;
  }
  int ans = 0;
  set<P> s;
  rep(i, 0, N) {
    auto h = uf.minimum[uf.findSet(i)];
    s.insert(h);
  }
  vector<P> v;
  rep(i, 0, N) {
    if (s.count(P(a[i], i)))
      continue;
    v.push_back(P(a[i], i));
  }
  sort(all(v));

  for (auto &o : s) {
    ans += o.first;
  }

  if (v.size() < uf.SizeOfCC - 2) {
    cout << "Impossible" << endl;
    return 0;
  }
  rep(i, 0, uf.SizeOfCC - 2) { ans += v[i].first; }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 10496
#include<stdio.h>
int main()
{
    long long a,b,c,k,cc,sum;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
    if(k<=a){
        sum=k;
    }
    else if(k>a&&k<=(a+b)){
        sum=a;
    }
    else{
        cc=k-(a+b);
        sum=a-cc;
    }
    printf("%lld",sum);
    return 0;
}

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

words = [input() for _ in range(n)]

d = {}

for i in range(n):
    if words[i] not in d:
        d[words[i]] = 1
    else:
        d[words[i]] += 1

m = max(d.values())
ANS = []

for keys in d.keys():
    if d[keys] == m:
        ANS.append(keys)

ANS = sorted(ANS)

for i in ANS:
    print(i)

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

using namespace std;

int main(){
	int a,b;
	cin>>a>>b;
	int d= a/b;
	double f=double(a) / b;
	int r= a % b;
	cout<<d<<' '<<r<<' ';
	cout<<fixed<<setprecision(5)<<f<<endl;
}



Measured memory_bytes: 3284
inp = list(map(int, input().split()))

N = inp[0]
K = inp[1]

sunuke_w_okashi = []

for okashi in range(K):
    _ = input()
    inp = inp = list(map(int, input().split()))
    sunuke_w_okashi = sunuke_w_okashi + inp

num_sunuke_wo_okashi = N - len(set(sunuke_w_okashi))

print(num_sunuke_wo_okashi)

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

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

    int sum = 1;
    for(int i = 0; i < n; i++){
        int tmp1 = sum * 2;
        int tmp2 = sum + k;
        if(tmp1 > tmp2){
            sum = tmp2;
        }
        else{
            sum = tmp1;
        }
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
s = str(input())
a = 0
b = 0

# 010101...
for i in range(len(s)):
    if i % 2 == 0 and int(s[i]) == 1:
        a += 1
    if i % 2 == 1 and int(s[i]) == 0:
        a += 1

# 101010...
for i in range(len(s)):
    if i % 2 == 0 and int(s[i]) == 0:
        b += 1
    if i % 2 == 1 and int(s[i]) == 1:
        b += 1
print(min(a, b))

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

#define EB emplace_back
#define int long long
#define F first
#define S second
#define N 500005
#define all(x) x.begin(),x.end()
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rt return
using namespace std;

const string yy = "Yes";
const string nn = "No";

int32_t main(){
	IOS;
	int tt = 1; 
	//cin >> tt;
	while(tt--){

    

    int a, b, c; cin >> a >> b >> c;
    cout << (a + b - 1) / b * c;
    
	}
	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,c=0;
  string S;
  cin >> N;
  cin >> S;
  for(int i =0;i<N-2;i++){
    if(S[i]=='A' && S[i+1]=='B' && S[i+2]=='C'){
        c++;
    }  
  }
  cout <<c;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<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.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

bool solve(){
  int n;
  cin>>n;
  vector<vector<int>> tree(n);
  vector<int> rev(n), cnt(n), a(n, -1);

  rep(i,n){
    int p; cin>>p; p--;
    tree[p].pb(i);
    cnt[p]++;
    rev[i] = p;
  }

  auto mex = [&](int v, vector<int> &num){
    vector<int> vv;
    for(auto d : tree[v]) vv.pb(num[d]);
    uniq(vv);
    int x = 0;
    while(x < vv.size() && vv[x]==x) x++;
    return x;
  };

  auto bfs = [&](queue<int> &q, vector<int> &num, vector<int> &c){
    int last = -1;
    while(!q.empty()){
      int v = q.front(); q.pop();
      num[v] = mex(v, num);
      c[rev[v]]--;
      if(c[rev[v]]==0 && num[rev[v]]==-1) q.push(rev[v]);
      last = v;
    }
    return last;
  };

  {
    queue<int> q;
    rep(i,n) if(cnt[i]==0) q.push(i);
    bfs(q,a,cnt);
  }

  int s = -1;
  rep(i,n) if(a[i]==-1) s=i;

  assert(s>=0);

  vector<int> vv;
  for(auto d : tree[s]) if(a[d]!=-1) vv.pb(a[d]);
  uniq(vv);
  int c1=0;
  while(c1 < vv.size() && vv[c1]==c1) c1++;
  int c2 = c1+1;
  while(c2-1 < vv.size() && vv[c2-1]==c2) c2++;


  rep(_,2){
    // try c1
    vector<int> b(a);
    vector<int> cc(cnt);
    cc[s] = 0;
    b[s] = c1;
    queue<int> q;
    q.push(rev[s]);

    int last = bfs(q,b,cc);
    if(b[last]!=b[s] && b[s]==mex(s,b)) return true;

    swap(c1,c2);
  }

  return false;
}

int main(){
  if(solve()) cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;

  return 0;
}


Measured memory_bytes: 14080
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <climits>
#include <iomanip>
#include <queue>

using namespace std;

const int N = 2e5 + 9;
const int INF = 2e9 + 2;
const int mod = 1e9 + 7;
const int K = 25;
const int P = 51;
const long long LONG_INF = LONG_MAX;
const int SZ = (1 << 18) - 1;

#define eb emplace_back
#define sz(s) (int)(s.size())
#define mkp make_pair
#define all(s) s.begin(), s.end()

#define ll long long

#define int ll

int cnt[N];

int a[N];

void solve() {
	int n, k;
	cin >> n >> k;
  	swap(n, k);
	for (int i = 1; i <= n; ++ i)
		cin >> a[i];
	int mn = INF;
	for (int i = 1; i <= n; ++ i)
		mn = min(mn, (a[n] - a[i] + (a[i] - a[1]) * 2, min(a[i] - a[1] + (a[n] - a[i]) * 2, min(k - a[i + 1] + a[i], a[i - 1] + k - a[i]))));
	cout << mn << '\n';
}


signed main() {
	ios_base::sync_with_stdio(false);
	solve();
	return 0;
}



Measured memory_bytes: 1792
import heapq

N, K = map(int, input().split())
sushi = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1], reverse=True)

eaten = [False]*N

#d1: 種類が増えないもの同士、d2: 同じ種類の中で最大の組み合わせ
d1, d2 = [0], [0]

for i in range(N):
    t, d = sushi[i]
    t -= 1
    if eaten[t]:
        d1.append(d1[-1]+d)
    else:
        eaten[t] = True
        d2.append(d2[-1]+d)


ans = 0
for i in range(1, K+1):
    if K-i >= len(d1):
        continue
    if i >= len(d2):
        continue
    ans = max(ans, d1[K-i]+d2[i]+i**2)
print(ans)


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

int main(void){
  int x,y;
  while(true) {
      cin >> x;
      cin >> y;
      if(x == 0 && y == 0){
          break;
      }
      if(x < y){
          cout << x << " " << y << endl;
      }
      else {
          cout << y << " " << x << endl;
      }
  }
}


Measured memory_bytes: 3008
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;

int main(int argc, char* argv[])
{
    int n, L;
    scanf("%d%d", &n, &L);

    vector<int> z;
    int i;
    int curr=L;
    ll sum=0;
    int min=INF;
    int save=0;
    for(i=0; i<n; i++) {
        z.push_back(curr);
        sum+=curr;
        if(min>abs(curr)) {
            min=abs(curr);
            save=curr;
        }
        curr++;
    }
    printf("%lld\n", sum-save);

    return 0;
}


Measured memory_bytes: 256
#include <iostream>


int main() {
    long long N, K, answer = 1;
    std::cin >> N >> K;

    for (int i = 0; i < N - 1; i++)
    {
        answer *= (K - 1);
    }
    answer *= K;

    std::cout << answer << std::endl;

    return 0;
}

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

using namespace std;
using ll = long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } }
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) { o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o; }
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) { o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o; }
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) { o << "{" << obj.first << ", " << obj.second << "}"; return o; }
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
void print(void) { cout << endl; }
template <class Head> void print(Head&& head) { cout << head; print(); }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head << " "; print(forward<Tail>(tail)...); }
void YN(bool flg) { cout << ((flg) ? "YES" : "NO") << endl; }
void Yn(bool flg) { cout << ((flg) ? "Yes" : "No") << endl; }
void yn(bool flg) { cout << ((flg) ? "yes" : "no") << endl; }

int main() {
	int N; cin >> N;
	V<ll> h(N), dp(N,0); REP(i, N) cin >> h[i];
	dp[1] = abs(h[1] - h[0]);
	FOR(i, 2, N) dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
	cout << dp[N-1] << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
  cin>>N;
  string ans="No";
  for(int i=1;i<=9;i++){
   if(N % i==0 && N/i<=9){
   ans="Yes"; break;
   }
     
  }cout<<ans<<endl;
  return 0;
}

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

int main() {
  int n, cnt = 0;
  cin >> n;
  
  vector<char> vec(n);
  for (int i = 0; i < n; i++) {
    cin >> vec.at(i);
  }
  
  for (int i = 0; i < n; i++) {
    if (vec.at(i) == 'R') cnt++;
  }

  if (cnt > n/2) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int line[3][4] = {{1,2,4,3},{0,3,5,2},{0,1,5,4}}; 

struct dice {
	int f2n[6];
};

bool check_equal_dice(dice& d1, dice& d2) {
	for (int f = 0; f < 3; ++f) {
		if ((d1.f2n[0] == d2.f2n[f])&&(d1.f2n[5] == d2.f2n[5-f])) {
			for (int i = 0; i < 4; ++i) {
				bool seq = true;
				for (int j = 0; seq && j < 4; ++j) {
					if (d1.f2n[line[0][j]] != d2.f2n[line[f][(i+j)%4]]) {
						seq = false;
					}
				}
				if (seq) {
					return true;
				}
			}
		}
		else if ((d1.f2n[0] == d2.f2n[5-f])&&(d1.f2n[5] == d2.f2n[f])) {
			for (int i = 0; i < 4; ++i) {
				bool seq = true;
				for (int j = 0; seq && j < 4; ++j) {
					int next = i-j;
					if (next < 0) {
						next = 4 + (i-j);
					}
					if (d1.f2n[line[0][j]] != d2.f2n[line[f][next]]) {
						seq = false;
					}
				}
				if (seq) {
					return true;
				}
			}
		}
	}
	return false;
}

int main(void) {
	int n;
	cin >> n;
	vector<dice> d(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 6; ++j) {
			cin >> d[i].f2n[j];
		}
	}
	bool find = false;
	for (int i = 0; !find && i < n-1; ++i) {
		for (int j = i+1; !find && j < n; ++j) {
			find = check_equal_dice(d[i],d[j]);
		}
	}

	if (!find) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}



Measured memory_bytes: 3108
import math as m 
a, b, x = map(int, input().split())
v = a*a*b

if x >= v/2:
  c =  2*(v-x)/(a**2)
  print(m.degrees(m.atan(c/a)))
else:
  c =  2*x/(a*b)
  print(m.degrees(m.atan(b/c)))

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

int main()
{
    int n, q;
    int order, index, value;

    cin >> n >> q;

    priority_queue<int> Q[n];

    for( int i = 0; i < q; i++ )
    {   
        cin >> order >> index;

        switch( order )
        {
            case 0:
                cin >> value;
                Q[index].push(value);
                break;
            case 1:
                if( Q[index].size() == 0 );
                else
                    cout << Q[index].top() << endl;
                break;
            case 2:
                if( Q[index].size() == 0);
                else
                    Q[index].pop();
                break;
        }
    }
    return 0;
}


Measured memory_bytes: 4112
#include <cmath>
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <numeric>

#define FOR(i,a,b) for(i=(a);i<(b);++i) 
#define FORR(i,a,b) for(i=(a);i>(b);--i)
#define REP(i,n) for(i=0;i<(n);++i)
#define REPR(i,n) for(i=(n);i>0;--i)
#define PB push_back
#define ll long long
#define INT_MAX 2147483647
#define LL_MAX 9223372036854775807

using namespace std;

long long GCD(long long a, long long b) {
	if (a < b)
		swap(a, b);
	if (b == 0) return a;
	else return GCD(b, a % b);
}
bool sosuu_check(int num) {
	int i;
	for (i = 2; i <= sqrt(num); ++i) {
		if (num%i == 0)
			return false;
	}
	return (num < 2) ? false : true;
}
int main() {
	unsigned long long ans, m, a, r, c, h;
	string s;
	int N,i;
	m = a = r = c = h = 0;
	cin >> N;
	REP(i, N) {
		cin >> s;
		if (s[0] == 'M') m++;
		if (s[0] == 'A') a++;
		if (s[0] == 'R') r++;
		if (s[0] == 'C') c++;
		if (s[0] == 'H') h++;
	}
	ans =	m * a * r + 
			m * a * c + 
			m * a * h +
			m * r * c +
			m * r * h +
			m * c * h +
			a * r * c + 
			a * r * h + 
			a * c * h +
			r * c * h;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define forr(i,a,n)	for(long long int i=a; i<n; i++)
#define loop(i,a,n)	for(long long int i=a; i>=n; i--)

int main() 
{
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(0);
	
	long long int a,b,c;
	cin>>a>>b>>c;
	long long int x=((a*c)/b)-a*(c/b);
	long long int y=((a*(min(c,b-1)))/b)-a*((min(c,b-1))/b);
	cout<<max(x,y);
	return 0;
}


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

using namespace std;
using ll = long long;

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

  int n, m;
  cin >> n >> m;
  vector<int> h(n);
  for (int i = 0; i < n; i++)
    cin >> h[i];

  vector<vector<int>> graph(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    bool f = true;
    for (auto e : graph[i]) {
      if (h[i] <= h[e])
        f = false;
    }
    if (f)
      ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 8724
/*
 _     _                             
| |__ | |__   __ _  __ _ _   _  __ _ 
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
                   |___/ |___/       
*/
#include<bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define BigInt      __int128
#define endl        '\n'
#define mii         map<ll int,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define sim         template < class c
#define ris         return * this
#define dor         > debug & operator <<
#define eni(x)      sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {

using namespace std;

sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug 
{
	~debug() 
	{ 
		cerr<<endl; 
	}
	eni(!=) cerr << boolalpha << i; ris; }
	eni(==) ris << range(begin(i), end(i)); }
	sim, class b dor(pair < b, c > d) 
	{
		ris << "(" << d.first << ", " << d.second << ")";
	}
	sim dor(rge<c> d) 
	{
	  	*this << "[";
	  	for (auto it = d.b; it != d.e; ++it)
	    	*this << ", " + 2 * (it == d.b) << *it;
	  	ris << "]";
	}
};
#define fuck(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define N  690005

ll int n, k;

ll int arr[N];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
	// cin>>TESTS;
	while(TESTS--)
	{
		cin >> n >> k;
		for(ll int i = 1; i <= n; i++)
		{
			cin >> arr[i];
		}
		ll int low = 1, high = hell;
		ll int ans = -1;
		while(low <= high)
		{
			ll int mid = (low + high) / 2;
			ll int cnt = 0;
			for(ll int i = 1; i <= n; i++)
			{
				ll int num = (arr[i] + mid - 1) / mid;
				cnt += (num - 1);
			}
			if(cnt <= k)
			{
				ans = mid;
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 5188
//~raam
//~created : Jun 03, 2020 - 6.44.26 PM IST

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

#define ll long long

int mat[12][12];

void solve(){
   int n, m, x;
   cin >> n >> m >> x;
   int cost[n];
   for(int i = 0; i < n; ++i){
      cin >> cost[i];
      for(int j = 0; j < m; ++j){
         cin >> mat[i][j];
      }
   }
   auto chk = [&](vector<int> &id){
      int total[m] = {};
      int price = 0;
      for(auto i : id){
         price += cost[i];
         for(int j = 0; j < m; ++j){
            total[j] += mat[i][j];
         }
      }
      for(int i = 0; i < m; ++i){
         if(total[i] < x){
            return 0;
         }
      }
      return price;
   };
   int ans = INT_MAX;
   for(int mask = 0; mask <= (1 << n); ++mask){
      vector<int> v;
      for(int bit = 0; bit < 12; ++bit){
         if((1 << bit) & mask){
            v.push_back(bit);
         }
      }
      int curans = chk(v);

      if(curans) ans = min(ans, curans);
   }
   if(ans == INT_MAX){
      cout << -1;
   }else{
      cout << ans;
   }
}

int main(){

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

   int t; t=1;
   while(t--)solve();
}


Measured memory_bytes: 3664
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define RG register
#define IL inline
#define inf 2147483640
#define LL long long
#define pi acos(-1.0)
#define db double
using namespace std;
IL int gi()
{
	RG int res=0,w=1;
	RG char ch;
	for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
	if(ch=='-') w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar()) res=10*res+ch-48;
	return res*w;
}
int n;
char s[200005];
int pos[27];
int dp[200005];
int appe[200005][27];
IL void dfs(RG int pos,RG int len)
{
	if(len==1)
		{
			for(RG int i=1;i<=26;++i)
				if(appe[pos][i]==(n+1))
					{printf("%c",'a'+i-1);return;}
		}
	for(RG int i=1;i<=26;++i)
		if(dp[appe[pos][i]]==len)
			{printf("%c",'a'+i-1);dfs(appe[pos][i]+1,len-1);break;}
}
int main()
{
	//freopen("3.in","r",stdin);
	//freopen("3.out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	for(RG int i=1;i<=26;++i) pos[i]=n+1;
	for(RG int i=1;i<=26;++i) appe[n+1][i]=n+1;
	dp[n+1]=1;
	for(RG int i=n;i>=1;--i)
		{
			for(RG int j=1;j<=26;++j)
				appe[i][j]=appe[i+1][j];
			appe[i][s[i]-'a'+1]=i;
			dp[i]=inf;
			for(RG int j=1;j<=26;++j)
				dp[i]=min(dp[i],dp[pos[j]]+1);
			pos[s[i]-'a'+1]=i;
		}
	RG int ans=inf;
	for(RG int i=1;i<=26;++i)
		if(pos[i]==(n+1)) {printf("%c",'a'+i-1);return 0;}
	for(RG int i=1;i<=26;++i)
		ans=min(ans,dp[pos[i]]);
	dfs(1,ans);
	//fclose(stdin);fclose(stdout);
	return 0;
}

Measured memory_bytes: 22272
#include <cstdio>
#include <cmath>
#include <iostream>

#define rep( i, n, m ) for (int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for (int i = ( n ); i < ( m ); i--)

int main( void ){
	int n;
	if(!scanf( "%d", &n ))
		return -1;
	int* B_array = new int[ n ];
	int* array = new int[ n ];
	rep( i, 0, n - 1 ){
		int a;
		if(!scanf( "%d", &a ))
			return -1;
		B_array[ i ] = a;
		array[ i ] = 0;
	}
	B_array[ n - 1 ] = 1000000;
	array[ n - 1 ] = 0;
	array[ 0 ] = B_array[ 0 ];
	int sum = array[ 0 ];
	rep( i, 1, n ){
		if(B_array[ i ] < B_array[ i - 1 ])
			array[ i ] = B_array[ i ];
		else
			array[ i ] = B_array[ i - 1 ];
		sum += array[ i ];
	}
	printf( "%d\n", sum );
	return 0;
}
// A 0 0   10 10 10 23
// B 0 153 10 10 23 inf


Measured memory_bytes: 256
N = int(input())
ans = 0

dic = {}

for i in range(N):

    dic[i] = []

    A = int(input())

    for j in range(A):
        x,y = map(int,input().split())
        dic[i].append([x,y])

ans = 0
for i in range(2 ** N):

    si = format(i,"b")
    si = si.zfill(N)

    num = 0
    for j in si:
        if j == "1":
            num += 1

    flag = True
    #print (si,dic)
    for j in range(N):

        if si[j] == "1":

            for k in dic[j]:
                x = k[0]
                y = k[1]

                
                if int(si[x-1]) != y:
                    #print (si,x-1,y)
                    flag = False

    if flag:
        ans = max(ans,num)

print (ans)


Measured memory_bytes: 3064
//
//  Swapping_Two_Numbers.c
//  AOJ
//
//  Created by admin on 2014/07/12.
//
//

#include <stdio.h>

main(){
    int a,b;
    
    do{
        scanf("%d %d",&a,&b);
        if(a==0 && b==0){
            break;
        } else if(b < a){
            printf("%d %d\n",b,a);
        } else {
            printf("%d %d\n",a,b);
        }
    }while(1);
    
    return 0;
}

Measured memory_bytes: 600
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (register ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (register ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (register int i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter putchar('\n')
#define siz(x) ((int)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef queue <int> qi ;
typedef queue <pii> qii ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int maxn = 3e5 + 100 ;
const int inf = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 1e9 + 7 ;
const double eps = 1e-7 ;
template <class T = int> T read()
{
	T f = 1, a = 0;
	char ch = getchar() ;
	while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
	while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
	return a * f ;
}

ll n;

ll a[maxn], sum[2], ans;

bool check(ll lim)
{
	ll sum = 0, pre = 0, val;
	rep(i, 1, n)
	{
		pre += val = a[i] * ((i & 1) ? -1 : 1);
		if(pre - val - sum <= lim) sum = max(sum, pre);
	}
	if(pre - sum <= lim) return 1;
	return 0;
}

signed main()
{
	scanf("%lld", &n);
	rep(i, 1, n) scanf("%lld", &a[i]), sum[i & 1] += a[i];
	if(!(n & 1))
	{
		printf("%lld %lld\n", max(sum[0], sum[1]), min(sum[0], sum[1]));
		return 0;
	}
	ll l = -1e9, r = 1e9;
	while(l <= r)
	{
		ll mid = (l + r) >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	ans = sum[0] - ans;
	printf("%lld %lld\n", ans, sum[0] + sum[1] - ans);
	return 0;
}

Measured memory_bytes: 2560
import java.util.Scanner;

public class Main{
	static int mod = 1000000000 + 7;
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		String S = sc.next();
		int[][] dp = new int[S.length() + 1][13];
		dp[0][0] = 1;

		for(int i = 1; i <= S.length(); i++) {
			char c = S.charAt(i - 1);
			if(c == '?') {
				for(int j = 0; j < 13; j++) {
					for(int k = 0; k < 10; k++) {
						dp[i][(10 * j + k) % 13] += dp[i - 1][j];
						dp[i][(10 * j + k) % 13] %= mod;
					}
				}
			}else {
				int a = c - '0';
				for(int j = 0; j < 13; j++) {
					dp[i][(10 * j + a) % 13] += dp[i - 1][j];
					dp[i][(10 * j + a) % 13] %= mod;
				}
			}
		}
		System.out.println(dp[S.length()][5]);
	}
}

Measured memory_bytes: 34976
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val n = readInteger()
    val aList = readLongList().sorted()
    var ans = 1L
    var pre = aList.first()
    for (a in aList.drop(1)) {
        if (a <= pre * 2) {
            ans++
        } else {
            ans = 1
        }
        pre += a
    }
    out.println(ans)
}

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 64020
#include<stdio.h>
int main(void){
	int n;
	scanf("%d",&n);
	int a[100],i;
	for(i=0;i<n;i++)
	scanf("%d",&a[i]);
	for(int j= 0;j<n/2;j++){
	int x = a[j];
	a[j] = a[n-j-1];
	a[n-j-1] = x;
	}

	for(int k=0;k<n;k++){
	if(k==n-1) printf("%d\n",a[k]);
	else printf("%d ",a[k]);
	}
	return 0;
}


Measured memory_bytes: 2048
//Code By: pratibha_899 (Pratibha Shrivastav)

/********   All Required Header Files ********/
#include<bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

//All the Loops and defines required
typedef long long int ll;
#define FOR(i, j, k, in) for (ll i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (ll i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007

//All the declarations using typedef

typedef pair<ll, ll> PII;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<ll, ll> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int l;
typedef unsigned long int ul;
typedef unsigned long long int  ull;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	int arr[n+1];
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	int min_cost[n+1];
	min_cost[1]=0;
	for(int i=2;i<=n;i++){
		if(i==2)
			min_cost[i]=abs(arr[2]-arr[1]);
		else{
			min_cost[i]=min((min_cost[i-1]+abs(arr[i-1]-arr[i])),(min_cost[i-2]+abs(arr[i-2]-arr[i])));
		}
	}
	cout<<min_cost[n];
	return 0;
}

Measured memory_bytes: 1024
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
signed main() {
    int A, B, K; cin >> A >> B >> K;
    vector<int> div;
    for(int i=1; i<=min(A, B); i++) {
        if(A % i == 0 and B % i == 0) div.push_back(i);
    }

    reverse(div.begin(), div.end());
    cout << div[K-1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

#define eps (1e-12)
int main(){
    double x1,y1,x2,y2,x3,y3;
    cin>>x1>>y1>>x2>>y2>>x3>>y3;
    double xa=x2-x1,ya=y2-y1,xb=x3-x1,yb=y3-y1;
    double area=0.5*abs(xa*yb-xb*ya);
    double a=hypot(xa,ya),b=hypot(xb,yb),c=hypot((xa-xb),(ya-yb));
    double r1=area*2/(a+b+c);
    double mx=max(a,max(b,c));
    double r2=mx*r1/(2.0*r1+mx);
    cout<<fixed<<setprecision(12)<<r2<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
constexpr int di[] = { 0, 1, 0, -1 }, dj[] = { 1, 0, -1, 0 };
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(), (v).end()
#define vmax 10000
constexpr ll inf = 1e18+7;
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/



int main(){
  ll n;
  cin>>n;
  if(n%2==0){
    cout<<n/2-1<<endl;
  }else{
    cout<<n/2<<endl;
  }
  return 0;
}


Measured memory_bytes: 256