akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;
int main(void){
    int i=0, l, a[10];
    int l2, b[2];

    cin>>l;

    if(l == 1){
      printf("Hello World");
    }
    else if(l == 2){

      for(int i = 0; i < 2; i++){
          cin >> b[i];
      }

      cout << b[0] + b[1] << endl;

    }

}


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

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

int xl[25], xr[25], h[25];
signed main(void)
{
	while(true) {
		int r, n;
		cin >> r >> n;
		if(!r && !n) break;
		REP(i, n) cin >> xl[i] >> xr[i] >> h[i];

		double hi = 60, low = 0;
		REP(i, 20) {
			double mid = (hi+low)/2;
			//cout << hi << " " << mid << " " << low << endl;
			bool flag = true;
			REP(j, 200000) {
				double x = -r + (double)(2*r)*j/200000;
				int ma = 0;
				REP(k, n) {
					if(xl[k] <= x && x <= xr[k]) {
						ma = max(ma, h[k]);
					}
				}
				double H = sqrt(r*r-x*x) + mid - r;
				// cout << ma << " " << H << endls
				if(ma < H) {flag = false; break;}
			}
			if(flag) {
				low = mid;
			} else {
				hi = mid;
			}
		}
		cout << fixed << setprecision(10) << low << endl;
	}


	return 0;
}

Measured memory_bytes: 3284
#include <bits/stdc++.h>
#include <iostream>
#include <functional>
#include <vector>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define rep1(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define per1(i,a,n) for (int i=a;i>n;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define endl "\n"
#define pi 3.14159265358979323846264338327950288419716939937510
#define IOS cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll mod=1000000007;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll qpow(ll a,ll b){ll s=1;while(b>0){if(b%2==1){s=s*a;}a=a*a;b=b>>1;}return s;}
ll qpowmod(ll a, ll b, ll c){ll res, t;res=1;t=a%c;while(b){if(b & 1){res=res*t%c;}t=t*t%c;b>>=1;}return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline long long read(){long long k=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}return k*f;}
inline void write(long long x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
// head
ll x,ans;
double now;
int main()
{
    //IOS;
    cin>>x;
    now=100;
    while(now<x)
    {
        now*=1.01;
        now=floor(now);
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}
/*

*/


Measured memory_bytes: 3636
n = int(input())
index=0
lists =[]
listForWords=[]
flag =0
while index<n:
    word = input()
    list1 = list(word)
    if index!=0:
        length = len(lists[index-1])
        if list1[0] == lists[index-1][length-1]:
            for li in listForWords:
                if word == li:
                    flag =1
        else:
            flag =1
    lists.append(list1)
    listForWords.append(word)
    index+=1

if flag==0:
    print("Yes")
else:
    print("No")


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

using namespace std;

int main()
{
    int A,B;
    cin>>A>>B;
    if(A > B){
        cout<<A+A-1<<endl;
    }else if(B > A){
        cout<<B+B-1<<endl;
    }else{
        cout<<A+B<<endl;
    }
      return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
unsigned long long a[100],n,m,p[1000];
string s;
int main()
{
	int i,j,k,ans=0;
	char c;
	cin>>n;
	unsigned long long nn=n;
	while(nn>0)
	{
		nn--;
		s+=(nn%26+'a');
		nn/=26;
	}
	for(i=s.size()-1;i>=0;i--)
		cout<<s[i];
	return 0;
}


Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
#include<string.h>

int main(){
	
	int n,num[200000]={0};
	int i,j,sum=0,ans[10000]={0};
	
	while(scanf("%d",&n)!=EOF){
		if(n==0)break;
	for(i=2;i<=110000;i++)num[i]=i;
	
	for(i=2;i<=sqrt(110000);i++){
		for(j=2;j*i<=110000;j++)num[i*j]=0;
	}
	
	for(i=0,j=0;i<=110000;i++){
		if(num[i]!=0){
			ans[j]=num[i];
			j++;
		}
		if(n==j)break;
	}
	for(i=0;i<j;i++)sum+=ans[i];
	
	printf("%d\n",sum);
		
		sum=0;
	}
return 0;
}

Measured memory_bytes: 1428
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <sstream>

using namespace std;

int main(){
	
	while(true){
		long long int n;
		cin >> n;
		
		if(n == 0){
			break;
		}
		
		long long int sum = -n;
		for(long long int i = 1; i < n; i++){
			if(i * i >= n){
				if(i * i == n){
					sum += i;
				}
				break;
			}
			if(n % i == 0){
				sum += i;
				sum += n / i;
			}
		}
		
		if(n > sum){
			cout << "deficient number" << endl;
		}else if(n == sum){
			cout << "perfect number" << endl;
		}else{
			cout << "abundant number" << endl;
		}
		
	}
	
	return 0;
}

Measured memory_bytes: 2996
#include "bits/stdc++.h"
// Custom Header {{{
#define ALL(x) x.begin(), x.end()
#define rep(i, s, n)      for(int i(s); i < int(n); ++i)
#define endl '\n'
#ifndef YDK
#define eprintf(...)
#endif
using namespace std;
using i64 = long long;
using pii = pair<i64, i64>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr const int INF  = 0x3f3f3f3f;
constexpr const i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr const int MOD  = int(1e9) + 7;
// }}}

// Library {{{
// }}}


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

    int ans = 0;
    int g = 0, p = 0;

    for (char c : s) {
        if (c == 'p') {
            if (p+1 <= g) {
                ++p;
            } else {
                ++g; --ans;
            }
        } else {
            if (p+1 <= g) {
                ++p; ++ans;
            } else {
                ++g;
            }
        }
    }

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


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

using namespace std;

int main(void){
    long long N, X, Y;
    cin >> N >> X >> Y;
    vector<long long> ans(N, 0);
    for(long long i = 1; i <= N - 1; i++){
        for(long long j = i + 1; j <= N; j++){
            long long d = min(j - i, abs(Y - j) + abs(X - i) + 1);
            // cout << i << " " << j << " " << d << endl;
            ans[d]++;
        }
    }
    for(int i = 1; i < N; i++) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define de cout<<"siktim seni\n";
ll int a,b,i,ans;
string s;
int main(){
	cin>>a>>s;
	for(i=0;i<a-2;i++){
		if(s[i]=='A' and s[i+1]=='B' and s[i+2]=='C'){
			ans+=1;
			i+=2;
		}
	}
	cout<<ans;
}

Measured memory_bytes: 256
grid_data = [[int(j) for j in input().split(" ")] for i in range(3)]

for i, c_list in enumerate(grid_data):
    grid_data[i] = [c - max(grid_data[i]) for c in c_list]

if all([True if grid_data[0] == c_list else False for c_list in grid_data]):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <algorithm>
#include <random>
#include <iomanip>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <chrono>
#include <cstdlib>
using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;
const double pi = acos(-1);
typedef pair<int, int> P;
#define REP(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define EPS 1e-4
#define OUTPUT(i) (cout << (ll)i << endl)
#define ALL(a) ((a).begin(), (a).end())

bool operator<(const pair<ll, ll> &a, const pair<ll, ll> &b)
{

    if (a.first == b.first)
        return a.second < b.second;

    return a.first < b.first;
}

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int arr[101];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);

    int N;
    cin >> N;

    for (int i = 0; i < N * (N - 1) / 2; ++i)
    {
        int A, B, C, D;
        cin >> A >> B >> C >> D;

        A--;
        B--;
        if (C > D)
        {
            arr[A] += 3;
        }
        else if (C < D)
        {
            arr[B] += 3;
        }
        else
        {
            arr[A] += 1;
            arr[B] += 1;
        }
    }
    vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.push_back(arr[i]);
    }
    sort(v.rbegin(), v.rend());

    int idx = 1;
    map<int, int> mp;
    for (int i = 0; i < N; ++i)
    {
        if (mp.find(v[i]) == mp.end())
            mp[v[i]] = idx;

        idx++;
    }

    for (int i = 0; i < N; ++i)
    {
        cout << mp[arr[i]] << endl;
    }

    return 0;
}


Measured memory_bytes: 3224
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

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

using namespace std;

int main()
{
	map<int,string> m;
	m[0] = "1111110";
	m[1] = "0110000";
	m[2] = "1101101";
	m[3] = "1111001";
	m[4] = "0110011";
	m[5] = "1011011";
	m[6] = "1011111";
	m[7] = "1110010";
	m[8] = "1111111";
	m[9] = "1111011";

	int n;
	while(cin >> n)
	{
		if(n == -1) break;

		string now = "0000000";
		bool flag[7];
		rep(i,7) flag[i] = false;

		rep(i,n)
		{
			int k;
			cin >> k;
		
			string ans = "0000000";
			rep(j,7)
			{
				if(now[j] != m[k][j])
				{
					ans[j] = '1';
				}
			}
			now = m[k];

			reverse(ans.begin(),ans.end());
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
#define MIN -1000000
using namespace std;
typedef long long ll;
typedef pair <int,ll> pil;
ll ans=0;
vector<pil> BC;
bool sortrule (const pil &BC1,const pil &BC2)
{
  return (BC2.second<BC1.second);
}
int main(void)
{
  int N,M;
  ll A[100005];
  cin >> N >> M;
  for (int i = 0; i < N; ++i)
    {
      cin >> A[i];
    }
  sort(A,A+N);
  for (int i = 0; i < M; ++i)
    {
      int b;
      ll c;
      cin >> b >> c;
      BC.push_back(pil(b,c));
    }
  sort(BC.begin(),BC.end(),sortrule);
  int now=0;
  while(1)
    {
      for(int i=0;i<int(BC.size());i++)
	{
	  for (int j = 0; j < BC[i].first; ++j)
	    {
	      if(A[now]<=BC[i].second)
		{
		  A[now]=BC[i].second;
		  now++;
		}
	      else
		{
		  now++;
		  break;
		}
	    }
	  if(now>=N) break;
	}
      break;
    }
  for (int i = 0; i < N; ++i)
    {
      ans+=A[i];
    }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3188
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let n: usize = parse!(it);
    let s: Vec<bool> = it.next().unwrap().chars().map(|x| x == 'o').collect();
    let mut ok = false;
    let mut ret = vec![];
    let next = |prev: bool, cur: bool, sym: bool| {
        if !(cur ^ sym) {
            prev
        } else {
            !prev
        }
    };
    'outer: for &i in &[true, false] {
        for &j in &[true, false] {
            let mut hyp = vec![false; n];
            hyp[0] = i;
            hyp[1] = j;
            for k in 1..(n - 1) {
                hyp[k + 1] = next(hyp[k - 1], hyp[k], s[k]);
            }
            if hyp[0] == next(hyp[n - 2], hyp[n - 1], s[n - 1])
                && hyp[1] == next(hyp[n - 1], hyp[0], s[0])
            {
                ok = true;
                ret = hyp;
                break 'outer;
            }
        }
    }
    if ok {
        println!(
            "{}",
            ret.into_iter()
                .map(|b| if b { 'S' } else { 'W' })
                .collect::<String>()
        );
    } else {
        println!("{}", -1);
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 4352
#include"bits/stdc++.h"

using namespace std;

int main() {
	int ab[10];

	for (int i = 1; i <= 4; i++) ab[i] = 0;
		for (int i = 0; i < 6; i++) {
			int n;
			cin >> n;
			ab[n]++;
		}

	if (ab[1] <= 2 && ab[2] <= 2 && ab[3] <= 2 && ab[4] <= 2) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import sys
N, M = map(int, input().split())
 
dp_f = [None] * (10**5 + 2)
dp_f[1] = 1
dp_f[2] = 1
for i in range(3, 10**5 + 1):
    dp_f[i] = dp_f[i-1] + dp_f[i-2]
def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif dp_f[n] is not None:
        return dp_f[n]
    v = f(n-1) + f(n-2)
    dp_f[n] = v
    return dp_f[n]
 
if M == 0:
    m = f(N+1)
    m %= 1000000007
    print(m)
    sys.exit(0)
 
A = [int(input()) for i in range(M)]
 
S = []
S.append(A[0])
for i in range(1, M):
    if A[i] == A[i-1] + 1:
        print(0)
        sys.exit(0)
    S.append(A[i] - A[i-1] - 1)
S.append(N - A[-1])
 
m = 1
for s in S:
    m *= f(s)
    m %= 1000000007
 
print(m)

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

vector<int> adj[200005];
vector<int> res;
int visited[200005]={0};

void dfs(int v)
{
    for(auto itr:adj[v])
    {
        if(visited[itr])continue;
        res[itr]+=res[v]; //
        visited[itr]=1;
        dfs(itr);
    }
}

int main()
{
    int n,q;
    cin>>n>>q;
    int a,b;
    for(int i=0;i<n-1;i++)
    {
        cin>>a>>b;
        a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int p,x;
    res.resize(n);
    for(int i=0;i<q;i++)
    {
        cin>>p>>x;
        p--;
        res[p]+=x;
    }
    visited[0]=1;
    dfs(0);//Yo !
    
    for(int i=0;i<n;i++)
    {
        cout<<res[i]<<" ";
    }
}


Measured memory_bytes: 21120
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int A[3];

int main() {
	cin >> A[0] >> A[1] >> A[2];
	sort(A, A + 3);
	cout << A[0] + A[1] << endl;
	return 0;
}

Measured memory_bytes: 3592
al, aa, bl, ba = map(int, input().split())

if al%ba == 0:
    bn = al//ba
else:
    bn = al//ba + 1

if bl%aa == 0:
    an = bl//aa
else:
    an = bl//aa + 1


if an <= bn:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9180
N, W = map(int, input().split())
V = [None]*N
ans = 0
for i in range(N):
    v, w = map(int, input().split())
    V[i] = [v/w, w]
V.sort(reverse=True)
for v, w in V:
    if W > w:
        W -= w
        ans += v*w
    else:
        ans += v*W
        break
print(ans)


Measured memory_bytes: 19880
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>

using namespace std;

typedef unsigned long long ull;

vector<int> T;

struct State{
  int cost, state, zero;
  State(int _cost, int _state, int _zero){
    cost = _cost;
    state = _state;
    zero = _zero;
  }
  bool const operator < (State s) const{
    return s.cost < cost;
  }
};

set<int> S;
int cx, cy;
int s, g ;

int dijkstra(){
  int dx[] = {-1, 1, -3, 3};
  int cost[] = {cx, cx, cy, cy};

  int zero;
  int tmp = s;
  for(int i = 8 ; i >= 0 ; i--){
    if(tmp % 10 == 0){
      zero = i;
      break;
    }
    tmp /= 10;
  }
  
  priority_queue<State> que;
  que.push(State(0, s, zero));
  
  while(!que.empty()){
    State q = que.top(); que.pop();
    if(q.state == g) return q.cost;
    
    if(S.find(q.state) == S.end()){      
      S.insert(q.state);      
      for(int i = 0 ; i < 4 ; i++){
	int pos = q.zero + dx[i];      
	if(pos < 0) pos += 9;
	if(pos >= 9) pos -= 9;
	int vv = q.state;
	vv /= T[pos];
	vv %= 10;
      
	int v = q.state;
	v -= T[pos] * vv;
	v += T[q.zero] * vv;
	
	que.push(State(q.cost + cost[i], v, pos));
      }
    }
  }
}

int main(){
  for(int i = 1 ; i <= 100000000 ; i *= 10){
    T.push_back(i);
  }
  reverse(T.begin(), T.end());

  while(cin >> cx >> cy, cx | cy){
    S.clear();
    s = g = 0;
    int v;
    for(int i = 0 ; i < 9 ; i++){
      cin >> v;
      s *= 10;
      s += v;
    }
    for(int i = 0 ; i < 9 ; i++){
      cin >> v;
      g *= 10;
      g += v;
    }
    
    cout << dijkstra() << endl;
    
  }
  return 0;
}

Measured memory_bytes: 25368
#include<stdio.h>
int main(void){
    char s[100],s1[50],s2[50];
    int n,check=0;
    scanf("%d",&n);
    scanf("%s",s);
    if(n%2==1){
        printf("No");
    }else{

        for(int i=0; i<n/2; i++){
        s1[i]=s[i];
        }
        for(int i=n/2; i<n; i++){
        s2[i-n/2]=s[i];
        }
        for(int i=0; i<n/2; i++){
            if(s1[i]!=s2[i]){
                check=1;
            }
        }
        if(check==0){
            printf("Yes");
        }else{
            printf("No");
        }
    }



    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>


#define REP(i,N) for(auto i = 0; i <N; i++)


typedef long long ll;
//const int MOD = pow(10,9)+7;
//const int MAX = 100001;

using namespace std;
int in(){
    int temp;
    scanf("%d",&temp);
    return temp;
}

ll lin(){
    ll temp;
    scanf("%lld",&temp);
    return temp;
}


int main() {
    
    ll N = lin();
   
    priority_queue<ll> pq;
    
    for(auto i = 0; i< N; i++){
        pq.push(lin());
    }

    
    vector<ll> lines;
    ll temp = -1;
    
    while(1){
        
        if (pq.size() == 0 || lines.size() == 2) break;
        
        if (pq.top() == temp){
            lines.push_back(temp);
            temp = -1;
            pq.pop();
            continue;
        }
        
        temp = pq.top();
        pq.pop();
        
    }
    
    
    if (lines.size()==2){
        cout << lines[0] * lines[1] << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
    
    
}









Measured memory_bytes: 1400
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int n, c;
int main() {
	auto I = [](){int i;cin>>i;return i;};
	set<int> S;
	cin >> n;
	while(n--) S.insert(I());
	cin >> n;
	while(n--)
		if (S.count(I())) ++c;
	cout << c << endl;
	return 0;
}

Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9+7;
const int MAX = 10000000;
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
//cout << 'H' << endl;
/*--------------------------------------------*/

int main(){
    //cout << fixed << setprecision(10)
    cin.tie(0);
    ios::sync_with_stdio(false);

	int N, K; cin >> N >> K;
	vector<int> x(N);
	rep(i,N) cin >> x[i];

	int m = min(N,K);
	
	ll ans = 0;

	rep(a,m+1){
		for(int b = 0;b <= m - a;b++){
			ll tmp = 0;
			priority_queue<int> pq;
			rep(i,a){
				tmp += x[i];
				if(x[i] < 0){
					pq.push(-1 * x[i]);
				}
			}
			for(int i = N-1;i >= N - b;i--){
				tmp += x[i];
				if(x[i] < 0){
					pq.push(-1 * x[i]);
				}
			}

			if(K - a - b > 0){
				int ct = 0;
				while(!pq.empty()){
					tmp += pq.top();pq.pop();
					ct++;
					if(ct + a + b == K) break;
				}
			}

			chmax(ans,tmp);
		}
	}

	cout << ans << endl;


}


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

int n,m,w,h,S;

struct Line{
  double a;
  double b;
  double l;
  double r;

  double gety(double x){
    return a*x+b;
  }
};
struct Point{
  double x;
  double y;

  bool operator < (const Point &a)const{
    return y < a.y;
  }
};


vector <Line> lr;
vector <Point> ar;

int main(){

  while(cin>>n>>m>>w>>h>>S, n|m|w|h|S){
    m += 2;
    lr.clear();
    lr = vector<Line>(m);
    ar.clear();
    ar = vector<Point>(n);
    lr[0].l = lr[0].b = lr[0].a = lr[0].r = 0;

    for(int i = 1; i < m-1; i++){
      double l,r;
      cin>>l>>r;
      lr[i].a = (r-l)/(double)w;
      lr[i].b = l;
      lr[i].l = l;
      lr[i].r = r;
    }
    lr[m-1].l = lr[m-1].b = lr[m-1].r = h;
    lr[m-1].a = 0;
    for(int i = 0; i < n; i++){
      double x, y; cin >> x >> y;
      ar[i].x = x; ar[i].y = y;
    }
    sort(ar.begin(), ar.end());
    vector< pair<int, double> > area(m-1, make_pair(0, 0));

    for(int i = 0; i < n; i++){
      int l = 0, r = m;
      while(l + 1 < r){
        int mid = (l+r)/2;
        if(ar[i].y >= lr[mid].gety(ar[i].x)){
          l = mid;
        }else{
          r = mid;
        }
      }
      area[l].first++;
    }
    for(int i = 0; i < m-1; i++){
      area[i].second = (lr[i+1].l - lr[i].l + lr[i+1].r - lr[i].r)*w/2.0;
    }

    /*
    for(int i = 0; i < area.size(); i++){
      cout << i+1 << ". " << area[i].first << " amds, " << area[i].second << " sqs" << endl;
    }
    */

    vector<double> areasum(area.size()+1, 0);
    vector<int> amsum(area.size()+1, 0);
    double totalarea = h*w;
    for(size_t i = 1; i < areasum.size(); i++){
      areasum[i] += areasum[i-1] + area[i-1].second;
    }
    for(size_t i = 1; i < amsum.size(); i++){
      amsum[i] += amsum[i-1] + area[i-1].first;
    }


    int ans =0;
    for(size_t bottom = 0; bottom < area.size(); bottom++){
      int l = bottom, r = amsum.size();
      while(l+1 < r){
        int mid = (l+r)/2;
        if(areasum[mid] - areasum[bottom] > totalarea - S){
          r = mid;
        }else{
          l = mid;
        }
      }
      ans = max(ans, amsum[l] - amsum[bottom]);
    }
    cout << n - ans << endl;
  }

  return 0;
}

Measured memory_bytes: 3772
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
 
using namespace std;
 
int main(){
 
    int array[5];
    scanf("%d %d %d %d %d",&array[0],&array[1],&array[2],&array[3],&array[4]);
 
    for(int i=1;i<=4;i++){
        for(int k=4;k>=i;k--){
            if(array[k]>array[k-1])swap(array[k],array[k-1]);
        }
    }
 
    for(int i=0;i<4;i++)printf("%d ",array[i]);
    printf("%d\n",array[4]);
 
    return 0;
}


Measured memory_bytes: 3216
#include <stdio.h>
#define MAX 100
#define INF 200000

int n, U[MAX][MAX];
void dijkstra();

int main(){
  int i, j, u, k, v, c;
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      U[i][j] = INF;
    }
  }
  
  for(i = 0; i < n; i++){
    scanf("%d%d",&u,&k);
    for(j = 0; j < k; j++){
      scanf("%d%d",&v,&c);
      U[u][v] = c;
    }
  }
  dijkstra();
  
  return 0;
}

void dijkstra(){
  int i, u, v, d[MAX], color[MAX], min;
  for(i = 0; i < n; i++){
    d[i] = INF;
    color[i] = 0;
  }
  d[0] = 0;
  color[0] = 1;
  while(1){
    u = -1;
    min = INF;
    for(i = 0; i < n; i++){
      if(color[i] != 2 && min > d[i]){
        u = i;
        min = d[i];
      }
    }
    if(u == -1) break;
    color[u] = 2;
    
    for(v = 0; v < n; v++){
      if(color[v] != 2 && U[u][v] != -1){
        if(d[v] > d[u] + U[u][v]){
          color[v] = 1;
          d[v] = d[u] + U[u][v];
        }
      }
    }
  }
  
  for(i = 0; i < n; i++) printf("%d %d\n",i, d[i]);
}

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

int main() {
    ll A, B, N;
    cin >> A >> B >> N;
    ll x = N;
    if (N >= B-1) x = B-1;
    ll ans = A*(x%B)/B;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define ll long long
#define ull long long unsigned
using namespace std;
#define foru(i,a,n) for (int i=(a); i<=(n); i++)
#define ford(i,n,a) for (int i=(n); i>=(a); i--)
#define rep(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define bit1cnt(x) (__builtin_popcountll(x))
#define sqr(x) ((x) * (x))
#define sz(x) ((int)(x.size()))
#define Pi 3.14159265358979
#define ii pair<int,int>
#define LL pair<ll,ll>
const int N = 2e5;
int a, b;
int main(){
    cin >>a >>b;
    int c = round(1.0*(a+b) / 2 );
    cout <<c;
    return 0;
}


Measured memory_bytes: 256
s = gets.chomp

s01 = "01"*(s.length/2)+"0"*(s.length%2)
s10 = "10"*(s.length/2)+"1"*(s.length%2)

repaint01 = 0
repaint10 = 0

(0..s01.length-1).each do |i|
  if s01[i] != s[i]
    repaint01+=1
  end
end

(0..s10.length-1).each do |i|
  if s10[i] != s[i]
    repaint10+=1
  end
end

p [repaint01,repaint10].min

Measured memory_bytes: 2428
#043c
N = int(input()) #N <= 100
a_list = list(map(int, input().split())) #-100 <= ai <= 100

#ループ数は200*100 = 20000.総当たりでOK
min_cost = 111*(200**2)

for y in range(min(a_list),max(a_list) + 1):
    cost = 0
    
    for x in a_list:
        cost += (x - y)**2
    
    if cost < min_cost:
        min_cost = cost

print(min_cost)

Measured memory_bytes: 3060
#インポート
import sys

#入力用
def ILI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def ISI(): return map(int, sys.stdin.readline().rstrip().split())
def II(): return int(sys.stdin.readline().rstrip())
def ISS(): return sys.stdin.readline().rstrip().split()
def IS(): return sys.stdin.readline().rstrip()

N = II()
K = II()
a = ILI()
ans = 0
for x in a:
    if x < K-x:
        ans += 2 * x
    else:
        ans += 2 * (K - x)
print(ans)

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

int sum_digit(int n){
  if( n == 0 ) return 0;
  else return n%10 + sum_digit(n/10);
}

int main()
{
  int N , A , B; cin >> N >> A >> B;
  
  int sum = 0;
  for( int i = 1; i <= N; i++ ){
  	if( A <= sum_digit(i) && sum_digit(i) <= B ) sum += i;
  }
  cout << sum << endl;
}

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

int main() {
	long long k, a, b, ans = 0;
	cin >> k >> a >> b;
	ans = k + 1;
	if ( a <= b && k >= min( a + 1, b - 1) ) {
		long long kk = k, c = 0;
		kk -= min( a + 1, b - 1 );
		c += b;
		long long cnt = kk / 2;
		c += kk % 2;
		c += cnt * (b - a);
		ans = max( ans, c );
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int F[N][10];
    int P[N][11];
    rep(i, N) {
        rep(j, 10) {
            cin >> F[i][j];
        }
    }
    rep(i, N) {
        rep(j, 11) {
            cin >> P[i][j];
        }
    }
    int MP[10];
    int ans = -INF;
    int anst = 0;
    int sumcnt = 0;
    for (int i = 1; i < 1024; i++) {
            int cnt[N] = {};
        sumcnt = 0;
        anst = 0;
        int tmp = i;
        rep(j, 10) {
            MP[j] = tmp % 2;
            tmp /= 2;
            //dump(MP[j]);
        }
        rep(k, N){
            rep(j, 10){
                if (MP[j] == 1 && F[k][j] == 1) {
                    cnt[k]++;
                    //printf("cnt[%d] = %d\n", j, cnt[k]);
                    sumcnt++;
                }
            }
        }
        rep(k ,N){
            //dump(cnt[k]);
            anst += P[k][cnt[k]];
            if (sumcnt > 0){
                //dump(anst);
            }
        }
        if  (sumcnt > 0) {
            ans = max(ans, anst);
        }
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main() {
    int n , w ; cin>>n>>w;
    vector<long long>dp(w + 1);
    for(int i = 0 ; i < n ; ++i){
        long long sz , cst ; cin>>sz>>cst;
        for(int wt = w - sz; wt >= 0 ; --wt){
            dp[wt + sz] = max(dp[wt + sz] , dp[wt] + cst);
        }

    }
    cout<<*max_element(dp.begin() , dp.end());
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
#include <climits>

using namespace std;

int main() {
    char a;
    cin >> a;
    if(a == 'A') {
        cout << 'T' << endl;
    } else if(a == 'T') {
        cout << 'A' << endl;
    } else if(a == 'C') {
        cout << 'G' << endl;
    } else if(a == 'G') {
        cout << 'C' << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int r[105];
int b[105];
map<string,int> m;
int32_t main(){
	int nr;cin>>nr;
	string tmp;
	for(int i=1;i<=nr;i++){
		cin>>tmp;
		m[tmp]++;
	}
	cin>>nr;
	for(int i=1;i<=nr;i++){
		cin>>tmp;
		m[tmp]--;
	}
	int ans=0;
	for(auto x:m){
		ans = max(ans,x.second);
	}
	cout<<ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrepi(i,a,b) for(int i=((int)(b)-1);i>=(a);--i)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) rrepi(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define ZERO(x) memset(x,0,sizeof(x))
#define MINUS(x) memset(x,-1,sizeof(x))
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end())
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){for(const auto& v : vv){ view(v); } }
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }
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; }
ll qp(ll a,ll b){ll ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
ll qp(ll a,ll b,ll mo){ll ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5;

int main() {
    ll a, b, c; cin >> a >> b >> c;
    ll l = 4 * a * b;
    ll r = c*c + a*a + b*b -2*c*a +2*a*b -2*b*c;
    if(c-a-b<=0) cout << "No" << endl;
    else if(l < r) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

int main() {
	ll N;
	cin >> N;
	vector<ll> A(N);
	rep(i, N) cin >> A[i];

	multiset<ll> t;
	for (auto a : A) {
		auto it = t.lower_bound(a);
		if (it != t.begin()) {
			t.erase(--it);
		}
		t.insert(a);
	}
	cout << t.size() << endl;

	return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i, n) for (int i = 0; i < ((int)(n)); i++) // 0-indexed昇順

int main()
{
    int a, b, h;
    cin >> a >> b >> h;
    cout << (a + b) * h / 2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    long int N;
    cin >> N;
 
    long int arr[N];
 
    long int o = 0;
    long int e = 0;
 
    for(long int n=0; n<N; n++)
    {
        cin >> arr[n];
 
        if(arr[n] % 2)
        {
            o++;
        }
    }
 
    if(o % 2)
    {
        cout << "NO";
    }
 
    else
    {
        cout << "YES";
    }
 
    return 0;
}

Measured memory_bytes: 4384
W,H,N=map(int,input().split())
dots=[list(map(int,input().split())) for i in range(N)]
#print(dots)
w=[0,W]
h=[0,H]

for i in range(N):
    if dots[i][2]==1:
        if w[0]<dots[i][0]:
            w[0]=dots[i][0]
    elif dots[i][2]==2:
        if w[1]>dots[i][0]:
            w[1]=dots[i][0]
    elif dots[i][2]==3:
        if h[0]<dots[i][1]:
            h[0]=dots[i][1]
    else:
        if h[1]>dots[i][1]:
            h[1]=dots[i][1]

if ((w[1]-w[0])>0)and((h[1]-h[0])>0):
    print((w[1]-w[0])*(h[1]-h[0]))
else:
    print("0")


Measured memory_bytes: 38256
import collections

n, x, y = list(map(int, input().split()))
lst = [
    min(abs(i - j), (abs(i - x) + abs(j - y) + 1))
    for j in range(2, n + 1)
    for i in range(1, j)
]
dic = collections.Counter(lst)
for k in range(1, n):
    print(dic[k])


Measured memory_bytes: 67816
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

const int INF = 1e9;

struct query {
  int v, d, c;
};

int main() {
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<VI> es(N+1);
  REP(i,0,M) {
    int a, b;
    cin >> a >> b;
    es[a].push_back(b);
    es[b].push_back(a);
  }
  int Q;
  cin >> Q;
  vector<query> qs(Q);
  FOR(q,qs) {
    cin >> q.v >> q.d >> q.c;
  }
  reverse(qs.begin(), qs.end());
  vector<VI> dp(N+1, VI(11, INF));
  REP(i,0,Q) {
    const auto q = qs[i];
    dp[q.v][q.d] = min(dp[q.v][q.d], i);
  }
  for(int i=9; i>=0; i--) {
    REP(x,1,N+1) {
      dp[x][i] = min(dp[x][i], dp[x][i+1]);
      FOR(y,es[x]) {
        dp[x][i] = min(dp[x][i], dp[y][i+1]);
      }
    }
  }
  REP(x,1,N+1) {
    if(dp[x][0] == INF) {
      cout << 0 << endl;
    } else {
      cout << qs[dp[x][0]].c << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 16248
#include <bits/stdc++.h>
#define mdsaqib std::ios::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define all(c) (c).begin(),(c).end()
#define endl '\n'
using namespace std;

signed main(){
    mdsaqib;
    string s;
    cin >> s;
    int n=s.size();
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=(s[i]-'0');
    }
    if(sum%9==0)cout << "Yes\n";
    else cout << "No\n";
}

Measured memory_bytes: 3780
fn solve(ni: i32) -> Option<i32> {
    let n = ni as f64;
    let x_sup = (n + 1.0) / 1.08;
    let x_min = n / 1.08;
    let candidates = vec![x_sup.floor(), x_min.ceil()];
    for i in candidates {
        let m = (i * 1.08).floor();
        if m == n {
            return Some(i as i32);
        }
    }
    None
}

#[test]
fn test_solve() {
    assert_eq!(solve(432), Some(400));
    assert_eq!(solve(1079), None);
    assert_eq!(solve(1001), Some(927));
}

fn main() {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    let n: i32 = input.trim().parse().unwrap();
    match solve(n) {
        Some(x) => println!("{}", x),
        None => println!(":(")
    }
}


Measured memory_bytes: 4352
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define stop char nyaa;cin>>nyaa;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

using P = pair<int, int>;

vector<int> x[3];
void solve() {
	int n; cin >> n;
	rep(i, 3) {
		x[i].resize(n);
		rep(j, n)cin >> x[i][j];
		sort(x[i].begin(), x[i].end());
	}
	ll ans = 0;
	rep(i, n) {
		int v = x[1][i];
		ll up = lower_bound(x[0].begin(), x[0].end(), v)-x[0].begin();
		ll dw = x[2].end() - upper_bound(x[2].begin(), x[2].end(), v);
		ans += up * dw;
		
	}
	cout << ans << endl;
}

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

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define pb push_back
#define Chkmax(a,b) a=a>b?a:b
#define Chkmin(a,b) a=a<b?a:b
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;

using namespace std;

namespace IO
{
    const uint32 Buffsize=1<<15,Output=1<<23;
    static char Ch[Buffsize],*S=Ch,*T=Ch;
    inline char getc()
    {
        return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
    }
    static char Out[Output],*nowps=Out;
    
    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

    template<typename T>inline void read(T&x)
    {
        x=0;static char ch;T f=1;
        for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
        for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
        x*=f;
    }

    template<typename T>inline void write(T x,char ch='\n')
    {
        if(!x)*nowps++='0';
        if(x<0)*nowps++='-',x=-x;
        static uint32 sta[111],tp;
        for(tp=0;x;x/=10)sta[++tp]=x%10;
        for(;tp;*nowps++=sta[tp--]^48);
        *nowps++=ch;
    }
}
using namespace IO;

inline void file()
{
#ifndef ONLINE_JUDGE
    FILE*DSA=freopen("water.in","r",stdin);
    FILE*SDU=freopen("water.out","w",stdout);
#endif
}

const int MAXN=1e5+7;

static int n;

static int a[MAXN];

vector<int>ed[MAXN];

inline void init()
{
	read(n);
	Rep(i,2,n)read(a[i]),ed[a[i]].pb(i);
}

static int dp[MAXN];

vector<int>w[MAXN];

void dfs(int u)
{
	for(register int v:ed[u])dfs(v),w[u].pb(dp[v]);
	sort(w[u].begin(),w[u].end());
	if(!w[u].empty())Rep(i,0,w[u].size()-1)
		Chkmax(dp[u],w[u].size()-i+w[u][i]);
}

inline void solve()
{
	dfs(1);
	printf("%d\n",dp[1]);
}

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


Measured memory_bytes: 18176
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
char b[100005];
int main()
{
	
	int n,sum=1;
	scanf("%d",&n);
	getchar();
	scanf("%s",b);
    for(int i=1;i<n;i++)
    {
    	
			if(b[i]!=b[i-1])
			sum++;
	}
	
	printf("%d\n",sum);
 } 

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

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

    int i = 0;
    int s, t, r;
    s = t = r = 0;
    for (int i = 0; i < N.size(); i++)
    {
        if (N[i] ==  'S')
            ++s;
        if (N[i] == 'T' and s > 0)
            --s, ++r;
    }
    int ans = N.size() - 2 * r;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
struct state{
  int y,x,dir,bit,cost;
};
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int H,W,L;
int sy,sx;
vector<int> cy[5],cx[5];

char t[30][30];
bool visited[30][30][3][(1<<5)];

int solve(){
  queue< state > Q;
  visited[sy][sx][0][0]=true;
  Q.push((state){sy,sx,0,0,0});

  while(!Q.empty()){
    state s=Q.front();Q.pop();

    if(t[s.y][s.x]=='G'&&s.dir==0)return s.cost;

    for(int i=0;i<5;i++)
      if(s.bit>>i&1){
	for(int j=0;j<(int)cy[i].size();j++)
	  t[cy[i][j]][cx[i][j]]='.';
      }

    if(s.dir==0){
      for(int i=0;i<4;i++){
	bool f=true;
	for(int j=1;j<=L;j++){
	  if(t[s.y+dy[i]*j][s.x+dx[i]*j]=='#'){
	    f=false;
	    break;
	  }
	}
	if(!f)continue;

	int ny=s.y+dy[i]*L;
	if(i==2)ny=s.y+1;

	int nx=s.x+dx[i]*L;
	if(i==1)nx=s.x+1;
	int ndir=2;
	if(i==1||i==3)ndir=1;
	if(visited[ny][nx][ndir][s.bit])continue;
	visited[ny][nx][ndir][s.bit]=true;
	Q.push((state){ny,nx,ndir,s.bit,s.cost+1});
      }

    }else if(s.dir==1){
      for(int i=0;i<4;i++){
	if(i==0||i==2){
	  bool f=true;
	  for(int j=0;j<L;j++){
	    if(t[s.y+dy[i]][s.x+j]=='#')f=false;
	  }
	  if(!f)continue;
	  int ny=s.y+dy[i];
	  int nx=s.x;
	  if(visited[ny][nx][s.dir][s.bit])continue;
	  visited[ny][nx][s.dir][s.bit]=true;
	  Q.push((state){ny,nx,s.dir,s.bit,s.cost+1});
	}else{

	  int ny=s.y;
	  int nx=s.x+dx[i];
	  if(i==1)nx=s.x+L;
	  if(nx>W)continue;
	  if(t[ny][nx]=='^'||t[ny][nx]=='#')continue;

	  int nbit=s.bit;
	  if('A'<=t[ny][nx]&&t[ny][nx]<='E'){
	    int id=t[ny][nx]-'A';
	    nbit=nbit^(1<<id);
	  }
	  if(visited[ny][nx][0][nbit])continue;
	  visited[ny][nx][0][nbit]=true;
	  Q.push((state){ny,nx,0,nbit,s.cost+1});
	}
      }
    }else{
      for(int i=0;i<4;i++){
	if(i==1||i==3){
	  bool f=true;
	  for(int j=0;j<L;j++){
	    if(t[s.y+j][s.x+dx[i]]=='#'){
	      f=false;
	      break;
	    }
	  }
	  if(!f)continue;

	  int ny=s.y;
	  int nx=s.x+dx[i];
	  if(visited[ny][nx][s.dir][s.bit])continue;
	  visited[ny][nx][s.dir][s.bit]=true;
	  Q.push((state){ny,nx,s.dir,s.bit,s.cost+1});
	}else{
	  int ny=s.y+dy[i];
	  int nx=s.x;
	  if(i==2)ny=s.y+L;
	  if(ny>H)continue;
	  if(t[ny][nx]=='^'||t[ny][nx]=='#')continue;

	  int nbit=s.bit;
	  if('A'<=t[ny][nx]&&t[ny][nx]<='E'){
	    int id=t[ny][nx]-'A';
	    nbit=nbit^(1<<id);
	  }
	  if(visited[ny][nx][0][nbit])continue;
	  visited[ny][nx][0][nbit]=true;
	  Q.push((state){ny,nx,0,nbit,s.cost+1});
	}
      }
    }

    for(int i=0;i<5;i++){
      for(int j=0;j<(int)cy[i].size();j++)
	t[cy[i][j]][cx[i][j]]='#';
    }
  }

  return -1;
}

int main(){
  for(int i=0;i<30;i++)
    for(int j=0;j<30;j++)
      t[i][j]='#';

  cin>>H>>W>>L;
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      cin>>t[i][j];
      if(t[i][j]=='S'){
	sy=i;
	sx=j;
      }

      if('a'<=t[i][j]&&t[i][j]<='e'){
	int id=t[i][j]-'a';
	cy[id].push_back(i);
	cx[id].push_back(j);
	t[i][j]='#';
      }
    }
  }
  cout<<solve()<<endl;
  return 0;
}

Measured memory_bytes: 1328
import sys
from io import StringIO
import unittest

MOD = 1000000007


def resolve():
    N, = map(int, input().split())
    tmp = [[8, 1], [1, 0]]
    nxt = [[0, 0], [0, 0]]
    for i in range(1, N):
        nxt[0][0] = (tmp[0][0] * 8) % MOD
        nxt[0][1] = ((tmp[0][0] * 1) % MOD + (tmp[0][1] * 9) % MOD) % MOD
        nxt[1][0] = ((tmp[0][0] * 1) % MOD + (tmp[1][0] * 9) % MOD) % MOD
        nxt[1][1] = ((tmp[0][1] * 1) % MOD + (tmp[1][0] * 1) % MOD + (tmp[1][1] * 10) % MOD) % MOD
        # print(nxt)
        tmp[0][0]=nxt[0][0]
        tmp[0][1] = nxt[0][1]
        tmp[1][0] = nxt[1][0]
        tmp[1][1] = nxt[1][1]

    print(tmp[1][1]% MOD)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """869121"""
        output = """2511445"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """3"""
        output = """54"""
        self.assertIO(input, output)



if __name__ == "__main__":
    resolve()


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

int main()
{
	long long int A,B, a[101], i, ans;
	cin >>A>>B;
	ans=0;
	for (i=1;i<=A;i++) 
	{
		cin >> a[i];
		ans+=min(2*a[i],abs(2*(B-a[i])));
	}
	cout << ans;
}

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

int sosuuCheck(int x);

int main(){
    int n;
    while(1){
        cin>>n;     if(n==0)break;

        int ans=0;
        for(int i=n+1;i<=n*2;i++){
            ans += sosuuCheck(i);
        }


        cout<<ans<<endl;
    }


    return 0;
}

int sosuuCheck(int x){


    if(x==1)return 1;
    else if(x==2)return 1;
    else if(x%2==0)return 0;
    else{
        int i=3;
        while(i<=sqrt(x)){
            if(x%i==0) return 0;

            i+=2;
        }
    }

    return 1;
}



Measured memory_bytes: 3032
#include<bits/stdc++.h>
using namespace std;
int main()
{
	cout<<fixed<<setprecision(6);
  	double w,h,x,y;
  	cin>>w>>h>>x>>y;
  	if(x==(w/2) && y==(h/2))
  	{
	    cout<<(w*h)/2<<" "<<1;
	}
	else
	{
		cout<<(w*h)/2<<" "<<0;
	}
	return 0;
}

Measured memory_bytes: 256
// Same Integers

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ios>
#include <iomanip>
#include <string>
#include <numeric>

using namespace std;

int main() {
    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2];

    // 2 5 4
    // 2 4 5  :sort
    // 3 5 5  + 1 1 0
    // 5 5 5  + 2 0 0


    // 2 6 3
    // 2 3 6  :sort
    // 2 4 7  + 0 1 1

    // 4 4 7  + 1 1 0
    // 5 5 7  + 1 1 0
    // 6 6 7  + 1 1 0
    // 7 7 7  + 1 1 0

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

    int res = 0;
    if (((a[1]-a[0]) % 2) != 0) {
        res++;
        a[1]++;
        a[2]++;
    }

    res += ((a[1] - a[0]) / 2);
    res += (a[2] - a[1]);
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
import java.math.*;import java.util.*;class Main{public static void main(String[]a){Scanner s=new Scanner(System.in);for(int t=s.nextInt();t-->0;){BigDecimal x=s.nextBigDecimal();BigDecimal y=s.nextBigDecimal();System.out.println((""+x).length()>80||(""+y).length()>80||(""+x.add(y)).length()>80?"overflow":x.add(y));}}}

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

int N;
vector<int> t[3];
vector<ll> dp[3];

int main(){
  cin>>N;
  for(int i=0;i<3;i++){
    t[i].resize(N);
    dp[i].resize(N+1,0);
    for(int j=0;j<N;j++)cin>>t[i][j];
    sort(t[i].begin(),t[i].end());
  }
  
  for(int i=0;i<N;i++)dp[2][i]=1;
  
  for(int i=1;i>=0;i--){
    
    for(int j=N-2;j>=0;j--){
      dp[i+1][j]+=dp[i+1][j+1];
    }
    
    for(int j=0;j<N;j++){
      dp[i][j]=0;
      int si=upper_bound(t[i+1].begin(),t[i+1].end(),t[i][j])-t[i+1].begin();
      dp[i][j]=dp[i+1][si];
    }
  }
  ll ans=0;
  for(int i=0;i<N;i++)ans+=dp[0][i];
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3712
#a,b=map(int,input().split())
n=int(input())
#s,t=list(input().split())
a=list(map(int,input().split()))
nex=1
ans=0
for i in range(n):
    if a[i]==nex:
        nex+=1
    else:
        ans+=1
if ans==n:
    print(-1)
    exit()
print(ans)




Measured memory_bytes: 24744
#include <iostream>
#include <vector>
#include <string>



using namespace std;
int N;
string S;


int main()
{

	cin >> N;
	cin >> S;
	
	string ans = S;

	for (int i = 0; i < S.size(); i++) {
		ans[i] = (ans[i] - 'A' + N) % 26 + 'A';
	}

	cout << ans << endl;

	return 0;


}


Measured memory_bytes: 256