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

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    int ans = 0;
    int d = 11141144;
    for (int i = 0; i < n; i++) {
        int tmp = abs(a[i] * n - sum);
        if (tmp < d) {
            d = tmp;
            ans = i;
        }
    }
    cout << ans << endl;
    return 0;
}

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

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

const ll inf = 1e15;
const ll mod = 1e9+7;

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

int main() {
    ll N; cin >> N;
    vector<ll> A(N); rep(i, N) cin >> A[i];
    
    vector<ll> sum(N+1, 0);
    rep(i, N) sum[i+1] = sum[i] + A[i];
    sort(sum.begin(), sum.end());
    
    ll ans = 0;
    ll x = sum[0];
    ll cnt = 1;
    rep(i, N) {
        if (x == sum[i+1]) cnt++;
        
        if (x != sum[i+1] || i == N-1) {
            ans += cnt * (cnt - 1) / 2;
            
            x = sum[i+1];
            cnt = 1;
        }
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3328
#include<iostream>
#include<stdio.h>//printf("%.15f\n",*********);
#include<vector>//文字列.erase(n),vector
#include<algorithm>//next_permutation
#include<set>
#include<string>//char(小文字-32=大文字)
                //to_string,string,substr
#include<sstream>
#include<complex>
#include<time.h>
#include<random>
#include<cmath>//min,max
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<locale>
#include<utility>//swap
#define rt "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)//start==1
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define drop(i,n) for(int i=n;0<i;i--)//end==1
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define Yay(ans) if(ans)cout<<"Yay!"<<rt;else cout<<":("<<rt;
#define sec(a,b,ans) if(ans)cout<<a<<rt;else cout<<b<<rt;
#define vcin(s,n) rep(i,n)cin>>s[i];//vcin(配列名),(繰り返し回数)
#define sort(s) sort(s.begin(),s.end())//標準=昇順
#define reve(s) reverse(s.begin(),s.end())//反転
#define str string
#define please return
#define AC 0
#define rapid_pleaseAC_fast cin.tie(0);ios::sync_with_stdio(false)
#define pi 3.1415926535897932384626//pi
#define nine 1000000000//10^9

using namespace std;
typedef vector<int> vint;
typedef long double ldouble;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<double> vdou;
typedef vector<double> vdouble;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<string>> vvstr;
typedef vector<vector<bool>> vvbool;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}

unsigned GetDigit(unsigned num) {
	return std::to_string(num).length();
}

int tow(int n) {//2のn乗
	if (n == 0)return 1;
	int x = tow(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;//@domino
}

int KETA(int n) { //Sum of Each Digit
	int sum = 0;
	while (n > 0) {
		sum += n % 10; n /= 10;
	}
	return sum;
}

unsigned ND(unsigned num) {//Number of Digits
	return std::to_string(num).length();//outmax=10
}//stringのほうが効率よくないか？

bool KIBN(string s) {
	rep(i, s.size() / 2) {
		if (s[i] != s[s.size() - 1 - i])return false;
	}
	return true;
}

/*

 (char)toupper(a[n])=文字列のn文字目を大文字で出力

  pow(a,b)=aのb乗

  */


int main(void) {
	rapid_pleaseAC_fast;
	
	int n, a, b;
	cin >> n >> a >> b;

	cout << min(a * n, b) << rt;

	please AC;
}
//参考：---

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

int main(){
  int a, b;
  cin >> a >> b;
  cout << a * b << " " << 2 * (a + b) << endl;
  return 0;
}



Measured memory_bytes: 3016
#!/usr/bin/env python3
import sys


def solve(N: int, v: "List[int]"):
    v.sort()

    res = v[0]
    for i in v[1:]:
        res += i
        res /= 2

    print(res)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    v = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, v)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
/*░░░░░░░▄▄▄▀▀▀▄▄███▄
░░░░░▄▀▀░░░░░░░▐░▀██▌
░░░▄▀░░░░▄▄███░▌▀▀░▀█
░░▄█░░▄▀▀▒▒▒▒▒▄▐░░░░█▌
░▐█▀▄▀▄▄▄▄▀▀▀▀▌░░░░░▐█▄
░▌▄▄▀▀░░░░░░░░▌░░░░▄███████▄
░░░░░░░░░░░░░▐░░░░▐███████████▄
░░░░░le░░░░░░░▐░░░░▐█████████████▄
░░░░toucan░░░░░░▀▄░░░▐██████████████▄
░░░░░░has░░░░░░░░▀▄▄████████████████▄
░░░░░arrived░░░░░░░░░░░░█▀██████*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll gcd(ll a, ll b)
{
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}
int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int n;
	scanf("%d", &n);
	ll res = 1;
	ll have1 = 0, have2 = 0;
	scanf("%lld %lld", &have1, &have2);
	for (int i = 2; i <= n; i++)
	{
		ll x, y;
		scanf("%lld %lld", &x, &y);
		ll l = 0, r = (ll)2e18 / (x + y);
		while (r - l > 1)
		{
			ll m = (l + r) / 2;
			if (m * (x + y) >= have1 + have2 && m * x >= have1 && m * y >= have2)
			{
				r = m;
			}
			else
			{
				l = m;
			}
		}
		have1 = r * x;
		have2 = r * y;
	}
	printf("%lld\n", have1 + have2);
}


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

int main(){
    int M, D;
    long counter = 0;

    cin >> M >> D;

    for(int m=1;m<=M;m++){
        for(int d=10;d<=D;d++){
            int d10 = d / 10;
            int d1 = d - d10*10;
            // cout << d1 << " " << d10 << endl;
            if(d1 >= 2 && d10 >= 2 && d1*d10 == m){
                counter++;
            }
        }
    }
    cout << counter << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define EPS 1e-6
#define INF 2147483647
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define llINF 9223372036854775807

using namespace std;
int main(){
  int n,a,b;
  cin>>n>>a>>b;
  vector<ll>vl;
  for(int i=0;i<n;i++){
    ll aaaaaa;cin>>aaaaaa;
    vl.pb(aaaaaa);
  }
  sort(vl.begin(),vl.end(),greater<ll>());
  double ma=0;
  for(int i=0;i<a;i++)
    ma+=vl[i];
  printf("%.7f\n",ma/(double)a);
  int acnt=0;
  int apointer=0;
  for(int i=0;i<n;i++){
    if(vl[i]==vl[a-1]&&acnt==0){
      apointer=i;acnt++;
    }else if(vl[i]==vl[a-1])acnt++;
  }
  ll cnt=0;
  if(acnt==1)cnt=1;
  else if(acnt==n){
    for(int i=a-1;i<b;i++){
      cnt+=(ll)1<<i;
    }
  }else if(apointer==0&&acnt!=n){
    ll aaacnt=1;
    for(int i=a;i<=acnt&&i<=b;i++){
      aaacnt=1;
      // int c=min(acnt)43 50-43
      int abc=min(i,acnt-i);
      for(int j=0;j<abc;j++){
	aaacnt*=(ll)(acnt-j);
	aaacnt=(ll)aaacnt/(j+1);
      }
      cnt+=aaacnt;
    }
  }else{
    cnt=1;
    int abc=min(a-apointer,acnt-(a-apointer));
    for(int i=0;i<abc;i++){
      cnt*=(ll)(acnt-i);
      cnt=(ll)cnt/(i+1);
    }
  }
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 256
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    n = int(input())
    s = input()
    ans = 0
    for i in range(n-2):
        if s[i]=='A' and s[i+1]=='B' and s[i+2]=='C':
            ans += 1
    print(ans)
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 38636
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i = (ll)(a); i < (ll)(b); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1LL << 60;
int main(){
    ll n,m; cin >> n >> m;
    map<ll,ll> pro_wa;
    rep(i,n) pro_wa[i] = 0; //i問目,ミス数0
    vector<pair<ll,string>> ps(m);
    rep(i,m) cin >> ps[i].first >> ps[i].second ;
    ll n_err = 0;
    ll n_ac = 0;
    for(auto x: ps){
        if (x.second=="WA"){
            if (pro_wa[x.first]!=-1) pro_wa[x.first]++;
        }else{
            if (pro_wa[x.first]==-1) continue;
            n_err += pro_wa[x.first];
            pro_wa[x.first] = -1;
            n_ac++;
        }
    }
    cout << n_ac << " " << n_err << endl;
    return 0;
}

Measured memory_bytes: 12800
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
#define lli long long int
#define llu unsigned long long int
#define sa(a,n,t) for(int ii=0;ii<n;ii++) scanf("%"#t"",&(a)[ii])
#define rep(i,n) for(int i=0;i<n;i++) 
#define reps(i,a,n) for(int i=a;i<n;i++) 
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rreps(i,a,n) for(int i=n-1;i>=a;i--)
#define validl(i,a,b) ((i>=a)&&(i<=b))?1:0
#define validmat(x,y,a,b,c,d) (validl(x,a,b) && validl(y,a,b))?1:0
#define validmn(x,y,m,n) validmat(x,y,0,m,0,n)
#define valid(i,n) validl(i,0,n)
#define v(t) vector<t>
#define vv(t) vector<vector<t> >
#define mk make_pair
#define pb push_back
#define pa(a,n,t)  for(int i=0;i<n;i++) printf("%"#t"",a[i])
#define p2 pair<int,int>
#define p3 pair<p2,int>
#define fi first
#define se second
#define sd(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld",a)
#define pd(a) printf("%d",a)
#define sf(a) scanf("%lf",&a)
#define pf(a) printf("%lf",a)
#define nline printf("\n")
#define ss(a) scanf("%s",a)
#define ps(a) printf("%s",a)
#define sc(a) scanf("%c",&a)
#define pc(a) printf("%c",&a)
#define mf(m,f) m.find(f)!=m.end()
#define pp3(m) cout<<m.fi.fi<<" "<<m.fi.se<<" "<<m.se<<" "
#define pp2(m) cout<<m.fi<<" "<<m.se<<" "
#define debug 0
int op(int a, int b) {
    return max(a, b);
}

int e() {
    return 0;
}

int main() {
    int n,k;
    cin>>n>>k;
    int a[300001]={0};
    segtree<int, op, e> seg(300001*2+10);
    rep(i,n) cin>>a[i];
    rep(i,n){
        int tmp=seg.prod((a[i]-k)>=0?(a[i]-k):0,a[i]+k+1)+1;
        seg.set(a[i],tmp);
        //cout<<b[a[i]]<<" ";
    }
    cout<<seg.all_prod()<<endl;
    return 0;
}


Measured memory_bytes: 14868
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

ll a[501][501] = {};
ll x1[1000000] = {};
ll y_1[1000000] = {};
ll x2[1000000] = {};
ll y2[1000000] = {};

int main() {
	ll h, w; cin >> h >> w;
	repe(i, 1, h)repe(j, 1, w) cin >> a[i][j];

	ll cnt = 0;
	repe(i, 1, h)repe(j, 1, w - 1) {
		if (a[i][j] & 1) {
			a[i][j + 1]++;
			y_1[cnt] = i;
			x1[cnt] = j;
			y2[cnt] = i;
			x2[cnt] = j + 1;
			cnt++;
		}
	}

	repe(i, 1, h - 1) {
		if (a[i][w] & 1) {
			a[i + 1][w]++;
			y_1[cnt] = i;
			x1[cnt] = w;
			y2[cnt] = i + 1;
			x2[cnt] = w;
			cnt++;
		}
	}
	cout << cnt << endl;
	rep(i, 0, cnt) {
		cout << y_1[i] << " " << x1[i] << " " << y2[i] << " " << x2[i] << endl;
	}

	return 0;
}

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

int main() {
    int n, l;
    cin >> n >> l;
    vector<string> vec(n);
    string ans;

    for(int i=0; i < n; i++) {
        cin >> vec.at(i);
    }

    sort(vec.begin(), vec.end());

    for(int j=0; j<n; j++) {
        ans += vec.at(j); 
    }

    cout << ans << endl;
 
}

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

int main()
{
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A, A + N);
    for (int i = 1; i < N; i++) {
        if (A[i - 1] == A[i]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 4240
# https://atcoder.jp/contests/abc153/tasks/abc153_c
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, k = map(int, input().split())
    hl = list(map(int, input().split()))
    hl.sort()
    rest = max(0, n-k)
    hl = hl[:rest]
    print(sum(hl))
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 88908
#include<bits/stdc++.h>
#define N 100005
#define inf 1000000000000000000ll
using namespace std;
int i,j,k,l,n,m,x,y,last[N],to[2*N],Next[2*N],fa[N],id[N],V[N],v[N];
int tot,q[N];
long long A[N],s[N];
struct node {
	int x,y;
}a[N];
inline void add(int x,int y) {
	Next[++tot]=last[x]; last[x]=tot; to[tot]=y;
}
inline bool cmp(int x,int y) {
	return max(a[x].x-a[x].y,0)<max(a[y].x-a[y].y,0);
}
inline int get(int x) {
	if (fa[x]==x) return x;
	return fa[x]=get(fa[x]);
}
int main() {
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	for (i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
	for (i=1;i<=n;i++) fa[i]=id[i]=i,V[i]=0;
	sort(id+1,id+1+n,cmp);
	for (i=1;i<=n;i++) {
		int r=0;
		V[id[i]]=1;
		for (j=last[id[i]];j;j=Next[j]) {
			if (!V[to[j]]) continue;
			if (v[get(to[j])]!=id[i]) {
				q[++r]=get(to[j]),v[get(to[j])]=id[i];
			}
		}
		long long S=0,M=inf;
		if (!r) {
			A[id[i]]=max(a[id[i]].x,a[id[i]].y);
			s[id[i]]=a[id[i]].y;
			continue;
		}
		for (j=1;j<=r;j++) S+=s[q[j]];
		if (r==1) {
			s[id[i]]=S+a[id[i]].y;
			for (j=1;j<=r;j++) fa[q[j]]=id[i];
			int p=max(a[id[i]].x,a[id[i]].y);
			A[id[i]]=min(max(1ll*a[id[i]].x,1ll*a[id[i]].y+A[q[1]]),S+p);
			continue;
		}
		int p=max(a[id[i]].x,a[id[i]].y);
		for (j=1;j<=r;j++) M=min(M,S-s[q[j]]+max(1ll*a[id[i]].x,1ll*a[id[i]].y+A[q[j]]));
		M=min(M,S+p);
		for (j=1;j<=r;j++) fa[q[j]]=id[i];
		s[id[i]]=S+a[id[i]].y;
		A[id[i]]=M;
	}
	printf("%lld\n",A[id[n]]);
}

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

typedef long long llt;

const int MaxN = 100000 + 5, MaxM = 100000 + 5;
const llt INF = 0x7F7F7F7F7F7F7F7F;

int N, M, Q;
llt A[MaxN], B[MaxM];

void init() {
  scanf("%d %d %d", &N, &M, &Q);
  for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
  for (int i = 1; i <= M; ++i) scanf("%lld", &B[i]);
}

inline llt getdis(llt a, llt b, llt x) {
  if (a > b) swap(a, b);
  if (a < x && x < b) return min(x - a, b - x) + b - a;
  if (b < x) return x - a;
  if (x < a) return b - x;
}

void solve() {
  for (int i = 1; i <= Q; ++i) {
    llt x; scanf("%lld", &x);
    int posa = lower_bound(A + 1, A + 1 + N, x) - A;
    int posb = lower_bound(B + 1, B + 1 + M, x) - B;

    llt ans = INF;
    if (posa <= N && posb <= M)
      ans = min(ans, getdis(A[posa], B[posb], x));
    if (posa > 1 && posb <= M)
      ans = min(ans, getdis(A[posa - 1], B[posb], x));
    if (posa <= N && posb > 1)
      ans = min(ans, getdis(A[posa], B[posb - 1], x));
    if (posa > 1 && posb > 1)
      ans = min(ans, getdis(A[posa - 1], B[posb - 1], x));
    printf("%lld\n", ans);
  }
}

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

Measured memory_bytes: 2816
// 　　＿＿
// 　／　<＠ﾌ
//  ｜(ﾉﾉハ))
//  ﾉ从ﾟヮﾟ从
// 　ﾉ｜ｿﾉГ|つ author:hotarunx
// 〈_ﾉ^^^ヽ|
// 　~~tｧtｧ~
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long
constexpr int INF = 1000000000 + 8;

// solution
// https://stackoverflow.com/questions/8006697/finding-maximum-distance-between-x-y-coordinates

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

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

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

    int ans = 0;

    int minx, miny, maxx, maxy;

    // x+y
    minx = maxx = x[0];
    miny = maxy = y[0];
    for (int i = 0; i < n; i++) {
        const int dist = x[i] + y[i];

        if (dist > maxx + maxy) {
            maxx = x[i], maxy = y[i];
        }
        if (dist < minx + miny) {
            minx = x[i], miny = y[i];
        }
    }

    ans = max(manhattan(minx, miny, maxx, maxy), ans);

    // x-y
    minx = maxx = x[0];
    miny = maxy = y[0];
    for (int i = 0; i < n; i++) {
        const int dist = x[i] - y[i];

        if (dist > maxx - maxy) {
            maxx = x[i], maxy = y[i];
        }
        if (dist < minx - miny) {
            minx = x[i], miny = y[i];
        }
    }

    ans = max(manhattan(minx, miny, maxx, maxy), ans);

    cout << ans << "\n";
}


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

int main(){
   int n,k;
   cin >> n >> k;
   int dp[n],h[n];
   memset(dp,0,sizeof dp);
   for(int i = 0; i < n; ++i){
      cin >> h[i];
   }
   dp[0] = 0;
   for(int i = 1; i < n; ++i){
      int c = k, j = i-1;
      dp[i] = 1e9;
      while(c-- and j >= 0){
         dp[i] = min(dp[j]+abs(h[i]-h[j]),dp[i]);
         --j;
      }
   }
   cout << dp[n-1];
}

Measured memory_bytes: 4408
#!/usr/bin/env python3
N=int(input())
p=list(map(int,input().split()))
LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]
E = [(v, i+1) for i, v in enumerate(p)]
E.sort()
ans=0
for v, i in E:
  r0 = RR[i]
  r1 = RR[r0]
  l0 = LL[i]
  l1 = LL[l0]
  RR[l0] = r0
  LL[r0] = l0

  ans += ((r1 - r0)*(i-l0)+(r0-i)*(l0 - l1))*v

print(ans)


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

int S[50];

int main()
{
  int n;
  S[0] = S[1] = 1;
  for (int i = 2; i < 45; i++){
    S[i] = S[i - 1] + S[i - 2];
  }
  cin >> n;
  cout << S[n] << endl;
}

Measured memory_bytes: 1160
using System;
using System.Linq;
using System.Collections.Generic;

namespace D2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] As = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            Array.Sort(As);
            int max = (int)Math.Pow(10,6) + 1;
            int[] cnt = new int[max];
            foreach( int a in As)
            {
                cnt[a] += 1;
            }
            List<int> unique = new List<int>();
            for(int i = 0; i < max; i++)
            {
                if(cnt[i] == 1)
                {
                    unique.Add(i);
                }
            }
            cnt =  new int[max];
            HashSet<int> aSet = As.ToHashSet();
            foreach(int a in aSet)
            {
                for(int m = a * 2; m < max; m += a)
                {
                    cnt[m] = 1;
                }
            }
            int ans = 0;
            foreach (int a in unique)
            {
                if(cnt[a] == 0)
                {
                    ans++;
                }
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 53732
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int h[100050];
int good[100050];
int main(){
    int n,m,a,b,ans=0;
    scanf("%d%d",&n,&m);
    memset(good,1,sizeof good);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    for(int i=0;i<m;i++){
        scanf("%d %d",&a,&b);
        if(h[a]<h[b]) good[a]=0;
        else if(h[a]>h[b]) good[b]=0;
        else good[a]=0,good[b]=0;
    }
    for(int i=1;i<=n;i++){
        if(good[i]) ans++;
    }
    printf("%d",ans);
}


Measured memory_bytes: 4536
#include <iostream>
#include <cmath>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#include <bitset>
#include <iomanip>
#include <map>
#include <queue>
#include <numeric>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::bitset;

#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define reps(i,s,e) for(int i=s; i<(int)e; i++)
#define coutd(i) cout << std::fixed << std::setprecision(i)
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;

template<class T>
using Graph = vector<vector<T>>;

const int INT_BIG = 1<<28;

int main() {
    string s;
    cin >> s;
    if (s == "ABC") {
        cout << "ARC" << endl;
    } else {
        cout << "ABC" << endl;
    }
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int count = b / a;
	if (c > count) {
		cout << count << endl;
	}
	else {
		cout << c << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define len(x) (int) (x.size())
using namespace std;
typedef long long ll;

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

    long double subans = L/3.0;
    long double ans = subans * subans * subans;

    printf("%.12Lf\n", ans);
    
    return 0;
}

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

int main(){
  int n;
  cin >>n;
  vector<int> w(n);
  rep(i,n) cin >>w[i];
  int curMin = 1e8;
  int sum = 0;
  rep(i,n) sum += w[i];
  int sum1 = 0;
  rep(i,n){
    sum1 += w[i];
    curMin = min(curMin, abs(2*sum1-sum));
  }
  cout << curMin << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int linearSearch(int* a, int n, int key)
{
    int i = 0;

    a[n] = key;
    while (a[i] != key) i++;
    return i != n;
}
int main()
{
    int n, q, key, sum = 0;

    cin >> n;
    int* s = new int[n + 1];
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> key;
        if (linearSearch(s, n, key)) {
            sum++;
        }
    }
    cout << sum << endl;

    return (0);
}


Measured memory_bytes: 3116
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <deque>
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFL 1100000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;


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

	int r, g, b;
	cin >> r >> g >> b;
	int ans = 100 * r + 10 * g + b;
	if (ans % 4 == 0) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int decide(int);
int main(){
  int n,x[10000],i,k = 0;
  scanf("%d",&n);
  
  for(i = 0;i < n;i++){
    scanf("%d",&x[i]);
    if(x[i] == 2){
      k++;
      continue;
    }
    if(x[i] < 2 || x[i] % 2 == 0) continue;
    k += decide(x[i]);
  }
  printf("%d\n",k);
  
  return 0;
}

int decide(int x){
  int i = 3;
  while(i <= sqrt((double)x)){
      if(x % i == 0) return 0;
      i = i + 2;
    }
  return 1;
}


Measured memory_bytes: 2044
#include<bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;
typedef pair< int, P > iP;
typedef pair< P, P > PP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int x, a, b;
    cin >> x >> a >> b;
    if( a >= b ) cout << "delicious";
    else {
        if( abs ( a - b ) > x ) cout << "dangerous";
        else cout << "safe";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long int
#define endl "\n"
using namespace std;
void solve()
{
	//Enter your code here Tanmay:)
	int n;
	cin>>n;
	int arr[n];
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
int count=1,min=arr[0];
	for(int i=1;i<n;i++)
	{
		if(arr[i]<=min)
			count++;

		if(arr[i]<min)
			min=arr[i];


	}
	cout<<count;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

#if defined(DEBUG)

#include <unistd.h>
#include <sys/fcntl.h>
#define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
#define DCALL(func, ...) func(__VA_ARGS__)

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#else  // defined(DEBUG)

#define DLOG(...)
#define DCALL(func, ...)

#endif // defined(DEBUG)

// g = eGCD(a, b, s, t)  --->  sa + tb = g
constexpr ll eGCD(ll a, ll b, ll& s, ll& t) {
  if (a == 0) {
    s = 0;
    t = 1;
    return b;
  }
  ll u = 0;
  ll g = eGCD(b % a, a, t, u);
  s = u - (b / a) * t;
  return g;
}

constexpr ll gcd(ll a, ll b) {
  ll dummy1 = 0;
  ll dummy2 = 0;
  return eGCD(a, b, dummy1, dummy2);
}

ll MOD;

struct Fp {
  ll val;

  Fp(ll t = 0) :
    val(t < 0 ? MOD + t % MOD : t >= MOD ? t % MOD : t) {}

  Fp& operator +=(const Fp& t) {
    val += t.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }

  Fp& operator -=(const Fp& t) {
    val -= t.val;
    if (val < 0) val += MOD;
    return *this;
  }

  Fp& operator *=(const Fp& t) {
    val = (val * t.val) % MOD;
    return *this;
  }

  Fp inv() const {
    if (val == 0) {
      cerr << "inv() is called for zero." << endl;
      exit(1);
    }
    ll u = 0;
    ll v = 0;
    eGCD(val, MOD, u, v);
    return Fp(u);
  }

  Fp& operator /=(const Fp& t) {
    return (*this) *= t.inv();
  }

  Fp operator +(const Fp& t) const { return Fp(val) += t; }
  Fp operator -(const Fp& t) const { return Fp(val) -= t; }
  Fp operator *(const Fp& t) const { return Fp(val) *= t; }
  Fp operator /(const Fp& t) const { return Fp(val) /= t; }
  Fp operator -() const { return Fp(-val); }

  bool operator ==(const Fp& t) const { return val == t.val; }
  bool operator !=(const Fp& t) const { return val != t.val; }
  
  operator ll() const { return val; }

};

int main(int argc, char *argv[]) {
#if defined(DEBUG)
  // GDB on Cygwin ignores redirection at run command.
  if (argc == 2) dup2(open(argv[1], 0), 0);
#else
  // For performance.  We should not use C-style stdio functions
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cout << setprecision(20);

  int p; cin >> p;
  MOD = p;
  vector<Fp> a(p), b(p), c(p);
  for (int i = 0; i < p; i++)  {
    int x; cin >> x;
    a.at(i) = (Fp)x;
  }
  b.at(0) = a.at(0);
  for (int i = 1; i < p; i++)  {
    c.at(i) = a.at(i) - b.at(0);
  }
  vector<vector<Fp>> powik(p, vector<Fp>(p));
  for (int i = 0; i < p; i++) {
    powik.at(i).at(0) = 1;
    for (int k = 1; k < p-1; k++) {
      powik.at(i).at(k) = i * powik.at(i).at(k-1);
    }
  }
  for (int k = 0; k < p-1; k++) {
    Fp s = 0;
    for (int i = 1; i <= p-1; i++) {
      s -= c.at(i) * powik.at(i).at(k);
    }
    b.at(p - 1 - k) = s;
  }
  for (int i = 0; i < p; i++) {
    if (i > 0) cout << " ";
    cout << (int)b.at(i);
  }
  cout << endl;

  return 0;
}



Measured memory_bytes: 70912
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <cmath>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}

ll gcd(ll a, ll b) {
  ll tmp;
  if ( b > a) {
    tmp = a;
    a = b;
    b = tmp;
  }
  while (a % b !=0) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}

ll lcm(ll a, ll b) {
  return a * b / gcd(a, b);
}

double dir(vector<int> x, vector<int> y, int d) {
  double ans = 0;
  for(int i=0; i<d; i++) {
    ans +=(x[i]-y[i])*(x[i]-y[i]);
  }
  return sqrt(ans);
}

int main(void) {
  int n;
  int d;
  cin>>n>>d;
  vector<vector<int>> v;
  

  for(int i=0; i<n; i++) {
    vector<int> x(d);
    for(int j=0; j<d; j++) {
      cin>>x[j];
    }
    v.push_back(x);
  }
  int cnt=0;
  for(int i=0; i<n; i++) {
    for(int j=i+1; j<n; j++) {

      double dirr = dir(v[i], v[j], d);
      if(dirr-floor(dirr)==0)
	cnt++;
    }
  }
  std::cout << cnt << std::endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <iterator>
#include <math.h>
#include <cstdlib>
#include <cmath>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define dump(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

int main(){
  int X;
  cin >> X;
  int ans = 0;
  FOR(i,1,32){
    int j = 2;
    if(i == 1){
      ans = max(ans,i);
    }else{
      while(pow(i,j) <= X){
        ans = max(ans,(int)pow(i,j));
        j++;
      };
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
    long long a, b, c;
    std::cin >> a >> b >> c;
    auto d = c - (a + b);

    if (d > 0 && a * b * 4 < d * d) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int ctoi(const char c) {
    if ('0' <= c && c <= '9') return (c - '0');
    return -1;
}
vector<int> input(int n) {
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec.at(i);
    }
    return vec;
}
void output(vector<int> vec) {
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
    return;
}
vector<vector<int>> input(int n, int m) {
    vector<vector<int>> table(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> table. at(i).at(j);
        }
    }
    return table;
}
void output(vector<vector<int>> table) {
    for (int i = 0; i < table.size(); i++) {
        for (int j = 0; j < table.at(0).size(); j++) {
            cout << table.at(i).at(j) << " ";
        }
        cout << endl;
    }
}
long long perm(int n, int r) {
    if (n < r) {
        cout << "error" << endl;
        return 0;
    }
    long long perm = 1;
    for (int i = n; i > n - r; i--) {
        perm *= i;
    }
    return perm;
}
long long comb(int n, int r) {
    if (n < r) {
        cout << "error" << endl;
        return 0;
    }
    long long comb = perm(n,r);
    for (int i = r; i > 0; i--) {
        comb /= i;
    }
    return comb;
}
long long homo(int n, int r) {
    return comb(n + r - 1, n - 1);
}
long long fact(int n) {
    long long fact = 1;
    for (int i = n; i > 0; i--) {
        fact *= i;
    }
    return fact;
}
int gcd(int a, int b)
{
    if (a % b == 0)
    {
        return(b);
    }
    else
    {
        return(gcd(b, a % b));
    }
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

long long lucas(int n){
  if(n==0){
    return 2;
  }
  if(n==1){
    return 1;
  }else{
    return lucas(n-1)+lucas(n-2);
  }
}


int main() {
  int n;
  cin >> n;
  vector<long long> l(87);
  l[0]=2LL;
  l[1]=1LL;
  for(int i=2;i<=n;i++){
    l[i]=l[i-1]+l[i-2];
  }
  cout << l[n] << endl;
}


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

int main() {

	int h, w; cin >> h >> w;
	vector<vector<char>> c(h + 2, vector<char>(w + 2, '#'));
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> c[i][j];
		}
	}
	for (int i = 0; i <= h + 1; i++) {
		for (int j = 0; j <= w + 1 ; j++) {		
			cout << c[i][j];
		}
		cout << endl;
	}
	return 0;
}

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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
// const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


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

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}


int main() {
  int64 A, B, C, K;
  cin >> A >> B >> C >> K;
  if(K <= A) {
    cout << K << endl;
  } else if(K <= A + B) {
    cout << A << endl;
  } else {
    cout << A - (K - (A + B)) << "\n";
  }
}

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

int main() {
    int n;
    cin >> n;
    vector<int> as(n);
    for (int i = 0; i < n; i++) {
        cin >> as[i];
    }

    reverse(as.begin(), as.end());
    long long mi = 2, ma = 2;
    for (int i = 0; i < n; i++) {
        long long g = mi / as[i] * as[i];
        if (g != mi && g + as[i] > ma) {
            cout << -1 << endl;
            return 0;
        }
        if (g != mi) mi = g + as[i];
        long long l = mi, r = 1e18;
        while (l < r - 1) {
            long long mid = (l + r) / 2;
            if (mid / as[i] * as[i] <= ma) {
                l = mid;
            } else {
                r = mid;
            }
        }
        ma = l;
    }
    cout << mi << ' ' << ma << endl;
}

Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF = 1 << 29;
const ll LL_INF = 1LL << 60;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N;
const int MAX_N = 5010;
struct State
{
    ll H, P;
    State() {}
    State(ll h, ll p) : H(h), P(p) {}
    bool operator<(const State &right) const
    {
        return H + P < right.H + right.P;
    }
};
vector<State> tasks;
ll dp[MAX_N][MAX_N];
void init()
{
    rep(i, MAX_N)
    {
        rep(j, MAX_N)
        {
            dp[i][j] = LL_INF;
        }
    }
}
int main()
{
    init();
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int h, p;
        cin >> h >> p;
        tasks.emplace_back(State(h, p));
    }
    sort(tasks.begin(), tasks.end());
    dp[0][0] = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (dp[i][j] == LL_INF)
            {
                continue;
            }
            ll h = tasks[i].H;
            ll p = tasks[i].P;
            if (dp[i][j] > h)
            {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                continue;
            }
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + p);
        }
    }
    for (int j = N; j >= 0; j--)
    {
        if (dp[N][j] != LL_INF)
        {
            cout << j << endl;
            return 0;
        }
    }
    return 0;
}


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

int main() {
  ll n; cin >> n;
  vector<ll> a(n);
  ll c = 0, ca = 0;
  rep(i,n) {
    cin >> a[i];
    ca += a[i];
  }
  ll ans = ca;
  rep(i,n) {
    c += a[i];
    ll d = ca - c;
    ans = min(abs(c - d), ans);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4772
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#define all(x) (x).begin(),(x).end()

void solve(){

}
int main(){
    int n;
    cin >> n;
    vector<int> a(n+1);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    a.push_back(105);
    int pre = a[0];
    int cnt = 1;
    int ans = 0;
    for (int i = 1; i <= n; i++){
        if(pre == a[i]){
            cnt++;
        } else if (pre != a[i]){
            pre = a[i];
            ans += cnt / 2;
            cnt = 1;
        }
    }
    cout << ans << endl;



    return 0;
}


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


int n;
int a[100005];
bool b[100005];
int q,k,o;


int main()
{
    cin>>n>>k>>q;
    for (int i=0;i<q;i++)
    {
        int x;
        cin>>x;
        a[x]++;
    }
    for (int i=1;i<=n;i++)
    {
        if (q-a[i]<k) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <functional>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

int partition(vector<int>& A, const int p, const int r)
{
	int x = A[A.size() - 1];
	int i = p - 1;
	for (int j = p; j < r; ++j)
	{
		if (A[j] <= x)
		{
			++i;
			int temp = A[i];
			A[i] = A[j];
			A[j] = temp;
		}
	}
	int temp = A[i + 1];
	A[i + 1] = A[r];
	A[r] = temp;
	return(i + 1);
}

void solve()
{
	int n;
	cin >> n;
	vector<int> A(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> A[i];
	}
	int pos = partition(A, 0, n - 1);
	for (int i = 0; i < n - 1; ++i)
	{
		if (i == pos)
		{
			cout << "[" << A[i] << "] ";
		}
		else
		{
			cout << A[i] << " ";
		}
	}
	if (pos == n - 1)
	{
		cout << "[" << A[n - 1] << "]" << endl;
	}
	else
	{
		cout << A[n - 1] << endl;
	}
}

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

Measured memory_bytes: 1532
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var N = int.Parse(Console.ReadLine());
            var list = new Dictionary<int, Item>();
            for (int i = 0; i < N; i++)
            {
                var inputs = Console.ReadLine().Split();
                var S = inputs[0];
                var P = int.Parse(inputs[1]);
                var val = new Item
                {
                    Name = S,
                    Score = P
                };
                list[i+1] = val;
            }

            foreach(var item in list.OrderBy(elem => elem.Value.Name).ThenByDescending(elem => elem.Value.Score))
            {
                Console.WriteLine(item.Key);
            }
        }
    }

    class Item
    {
        public string Name { get; set; }
        public int Score { get; set; }
    }
}


Measured memory_bytes: 13536
#include<bits/stdc++.h>
using namespace std;
struct edge{int to,cost;};
#define MAX 2005
#define INF (1<<26)
int N,M,K;
vector<edge> G[MAX];

int Size[MAX];
int V[MAX][MAX];
int DP[MAX][MAX];
int dp[MAX][MAX][2];

bool visited[MAX];
vector<int> A,B;

void dfs(int pos,int prev){
  if(visited[pos]){
    return;
  }
  visited[pos]=true;
  A.push_back(pos);
  for(int i=0;i<(int)G[pos].size();i++){
    if(G[pos][i].to==prev)continue;
    B.push_back(G[pos][i].cost);
    dfs(G[pos][i].to,pos);
  }
}
int main(){
  
  cin>>N>>M>>K;
  for(int i=0;i<M;i++){
    int a,b,c;
    cin>>a>>b>>c;
    G[a].push_back((edge){b,c});
    G[b].push_back((edge){a,c});
  }
  fill(V[0], V[MAX], -INF);
  int C=0;
  for(int i=1;i<=N;i++){
    if(visited[i])continue;
    if(G[i].size()==2)continue;
    A.clear();
    B.clear();
    
    dfs(i,0);
    int size=A.size();    
    Size[C] = size;
    for(int j=0;j<=size+1;j++)
      for(int k=0;k<=size+1;k++)
        dp[j][k][0]=dp[j][k][1]=-INF;

    dp[0][0][0]=0;

    for(int j=0;j<size;j++){
      for(int k=0;k<=size;k++){
        for(int l=0;l<2;l++){
          if(dp[j][k][l]==-INF)continue;
          // not select
          dp[j+1][k][0]=max(dp[j+1][k][0],dp[j][k][l]);
          // select
          if(l==1&&j>0&&B[j-1]==0)continue;
          int ncost=dp[j][k][l];
          if(l==1&&j>0){
            ncost+=B[j-1];
          }
          dp[j+1][k+1][1]=max(dp[j+1][k+1][1],ncost);
          
        }
      }
    }

    for(int k=0;k<=size;k++){
      for(int l=0;l<2;l++){
        V[C][k] = max(V[C][k], dp[size][k][l]);
      }
    }

    C++;
  }

  for(int i=1;i<=N;i++){
    if(visited[i])continue;
    A.clear();
    B.clear();
    
    dfs(i,0);
    int size=A.size();    
    Size[C] = size;

    for(int s = 0; s < 2; ++s) {
      for(int j=0;j<=size;j++)
        for(int k=0;k<=size;k++)
          dp[j][k][0]=dp[j][k][1]=-INF;

      dp[1][s][s]=0;
      for(int j=1;j<size;j++){
        for(int k=0;k<=size;k++){
          for(int l=0;l<2;l++){
            if(dp[j][k][l]==-INF)continue;
            // not select
            dp[j+1][k][0]=max(dp[j+1][k][0],dp[j][k][l]);
            // select
            if(l==1&&j>0&&B[j-1]==0)continue;
            int ncost=dp[j][k][l];
            if(l==1&&j>0){
              ncost+=B[j-1];
            }
            if(j+1 == size) {
              if(s==1&&j>0&&B[j]==0)continue;
              if(s==1&&j>0){
                ncost+=B[j];
              }
            }
            dp[j+1][k+1][1]=max(dp[j+1][k+1][1],ncost);
          }
        }
      }
      for(int k=0;k<=size;k++){
        for(int l=0;l<2;l++){
          V[C][k] = max(V[C][k], dp[size][k][l]);
        }
      }
    }

    C++;
  }

  fill(DP[0], DP[MAX], -INF);
  DP[0][0] = 0;
  for(int i = 0; i < C; ++i) {
    for(int j = 0; j <= K; ++j) {
      if(DP[i][j] == -INF) continue;
      for(int k = 0; k <= Size[i] && j+k <= K; ++k) {
        DP[i+1][j+k] = max(DP[i+1][j+k], DP[i][j] + V[i][k]);
      }
    }
  }
  if(DP[C][K] == -INF) cout << "Impossible" << endl;
  else cout << DP[C][K] << endl;


  return 0;
}

Measured memory_bytes: 64256