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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, n, 0)
#define dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9;

ll modpow(ll a, ll n)
{
  ll res=1;
  while (n>0) {
    if (n&1) res = res*a % mod;
    a = a*a % mod;
    n >>= 1;
  }
  return res;
}

void solve()
{
  int n; cin>>n;
  vector<int> a(n, 0);
  rep(i,n) cin>>a[i];
  sort(a.begin(),a.end());
  rep(i,n) {
    if (a[i]!=i+(i+(n+1)%2)%2) {
      cout << 0 << endl;
      return;
    }
  }
  cout << modpow(2,n/2) << endl;
}

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


Measured memory_bytes: 640
program ABC_069_C_4adjacent
   implicit none
   integer N, i, countN2, countN4
   integer(8), allocatable :: a(:)
   read(*, *) N
   allocate(a(1: N))
   read(*, *) a(1: N)
   countN2 = 0
   countN4 = 0
   do i = 1, N
       if(mod(a(i), 2) == 0) then
	       countN2 = countN2 + 1
	   end if
	   if(mod(a(i), 4) == 0) then
	       countN4 = countN4 + 1
	   end if
   end do
   if(N/2 <= countN4) then
       write(*, *) 'Yes' 
   else if(N - 2*countN4 <= countN2 - countN4) then
       write(*, *) 'Yes'
   else
       write(*, *) 'No'
   end if
end program ABC_069_C_4adjacent

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
  cin>>N;
  vector<int>H(N);
  for(int i=0;i<N;i++)
    cin>>H.at(i);
  bool x=true;
  for(int i=N-1;0<i;i--){
  if(H.at(i)-H.at(i-1)<=-2){
  x=false; break;
  }else{
  if(H.at(i)-H.at(i-1)==-1)
    H.at(i-1)--;
  }
    
  
  }if(x) 
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;

return 0;
}

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

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> d(N);

    for (int i = 0; i < N;i++){
        cin >> d[i];
    }
    sort(d.rbegin(), d.rend());
    int cnt=0,tmp;
    for (int i = 0; i < N;i++){
        if(d[i]==d[i+1]&&tmp!=d[i]){
            tmp = d[i];
            i++;
            cnt++;
        }else if(d[i]!=tmp){
            cnt++;
        }
    }
    cout << cnt;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
int main(){
  long n;
  std::cin >> n;
  std::vector<long> a(n);
  for(long i = 0; i < n; ++i){
    std::cin >> a[i];
  }
  long absMin = 1000000000;
  long minusCount = 0;
  long sum = 0;
  for(long i = 0; i < n; ++i){
    long minus = (a[i] < 0);
    long abs = (minus ? -a[i] : a[i]);
    if(abs < absMin)
      absMin = abs;
    if(minus)
      ++minusCount;
    sum += abs;
  }
  if(minusCount%2 == 1){
    sum -= 2*absMin;
  }

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


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


/*
string t = "AKIHABARA";


int main()
{
  string s;cin >> s;
  int j = 0;
  for (int i = 0; i < t.length(); i++) 
  {
    if (s[j] == t[i])
    {
      j++;
      continue;
    }
    else if (t[i] == 'A')
    {
      continue;
    }
    else
    {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
    
}
*/

vector<string> t = {"AKIHABARA",
"KIHABARA",
"AKIHBARA",
"AKIHABRA",
"AKIHABAR",
"KIHBARA",
"AKIHBRA",
"KIHABAR",
"KIHBRA",
"AKIHBR",
"KIHABR",
"KIHBAR",
"KIHBR",
"AKIHABR"};

int main()
{
  string s; cin >> s;
  for (auto && a : t) 
  {
    if (a == s)
    {
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}

Measured memory_bytes: 3632
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
		    arr[i] = sc.nextInt();
		}
		for (int i = 2; i <= m; i++) {
		    for (int j = 0; j < n - 1; j++) {
		        if (arr[j] % i > arr[j + 1] % i) {
		            int tmp = arr[j];
		            arr[j] = arr[j + 1];
		            arr[j + 1] = tmp;
		        }
		    }
		}
		StringBuilder sb = new StringBuilder();
		for (int x : arr) {
		    sb.append(x).append("\n");
		}
		System.out.print(sb);
	}
}



Measured memory_bytes: 26364
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}



signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  int x,y,z;cin>>x>>y>>z;
  cout<<z<<" "<<x<<" "<<y<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

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

#define MOD 100000007

typedef pair<int,int> P;

int h, w;
int sx, sy, gx, gy;
int closed[1002][1002];
int minDist[1002][1002];

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

int main(){
  while(cin >> h >> w >> sy >> sx >> gy >> gx){
    queue<P> open;
    open.push(P(sx, sy));

    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
	minDist[i][j] = INT_MAX;
	closed[i][j] = 0;
      }
    }

    closed[sy][sx] = 1;
    minDist[sy][sx] = 0;

    while(!open.empty()){
      P p = open.front();
      open.pop();

      if(p.first == gx && p.second == gy){
	break;
      }

      int ncost = minDist[p.second][p.first] + 1;

      for(int i = 0; i < 4; i++){
	int nx = (p.first + dx[i] + w) % w;
	int ny = (p.second + dy[i] + h) % h;

	if(minDist[ny][nx] < ncost) continue;
	if(minDist[ny][nx] > ncost) open.push(P(nx, ny));

	closed[ny][nx] += closed[p.second][p.first];
	closed[ny][nx] %= MOD;
	minDist[ny][nx] = ncost;
      }
    }

    cout << closed[gy][gx] << endl;
  }
}

Measured memory_bytes: 9080
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <tuple>
#include <list>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

#define xx first
#define yy second
#define $1 first
#define $2 second

const ll MOD = 1e9 + 7;
ll fast_power(ll base, ll power) {
	ll result = 1;
	while (power > 0) {
		if (power & 1) {
			result = (result*base) % MOD;
		}
		base = (base*base) % MOD;
		power >>= 1;
	}
	return result;
}
void solve() {
	ll n, k; cin >> n >> k;
	ll ans = 0;
	for (ll i = k; i <= n+1; i++) {
		ans += (( (n*(n + 1) / 2) - ((n - i)*(n - i + 1) / 2)) - ((i - 1)*i / 2)) + 1;
		ans %= MOD;
	}
	cout << ans%MOD;
}
int main() {

#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	solve();
}

Measured memory_bytes: 3644
#pragma GCC optimize("O3")
#define first x
#define second y
#include <bits/stdc++.h>

using namespace std;

signed main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = abs(a - b) + abs(b - c);
    ans = min(ans, abs(a - c) + abs(c - b));
    ans = min(ans, abs(b - a) + abs(a - c));
    ans = min(ans, abs(b - c) + abs(c - a));
    ans = min(ans, abs(c - a) + abs(a - b));
    ans = min(ans, abs(c - b) + abs(b - a));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<numeric>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define int64 long long
#define yokuwaruprime (10*10*10*10*10*10*10*10*10+7)
using namespace std;

int main(){
  int64 a,b,c;
  cin>>a>>b>>c;
  if(a%2==0||b%2==0||c%2==0){
    cout<<0;
  }else{
    cout<<min(a*b,min(b*c,c*a));
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1e14;
const ll MOD = 1e9 + 7;
#define MAX_N 45
int dp[MAX_N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    dp[0] = dp[1] = 1;
    for (int i = 2; i < n + 1; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout << dp[n] << endl;
    return 0;
}


Measured memory_bytes: 3168
#include<bits/stdc++.h>
using namespace std;
string s;
int div(){
    string t = s;
    int n= s.size();
    int ans = 1;
    string l = to_string(s.at(0));
    s = s.substr(1);
    
    while(s.size()){
        if(to_string(s.at(0))==l){
            if(s.size()==1){
                if(t.at(n-3)+t.at(n-2)==l.at(0)+s.at(0)){
                    ans++;
                    break;
                }
                else break;
            }
            l=to_string(s.at(0))+to_string(s.at(1));
            s=s.substr(2);
            ans++;
        }
        else{
            l=to_string(s.at(0));
            s=s.substr(1);
            ans++;
        }
    }
    return ans;
}
int main(){
    cin>>s;
    cout << div() << endl;
}

Measured memory_bytes: 1084
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std ;

const int P = 1000000007 ;

int n ;
int yes[600000] ;
int base[600000] ;

int expow(int a, int b){
    int res = 1 ;
    while (b){
        if (b & 1)
            res = 1ll * a * res % P ;
        a = 1ll * a * a % P ; b >>= 1 ;
    }
    return res ;
}
int main(){
    cin >> n ;
    for (int i = 1 ; i <= n ; ++ i) scanf("%d", &base[i]) ;
    sort(base + 1, base + n + 1) ;
    if (n & 1){
        yes[1] = 0 ; int cnt = 0 ;
        for (int i = 2 ; i <= n ; i += 2)
            yes[i] = yes[i + 1] = 2 * (++ cnt) ;
        for (int i = 1 ; i <= n ; ++ i)
            if (base[i] != yes[i]) return printf("0\n"), 0 ;
    }
    else{
        int cnt = 0 ;
        yes[1] = yes[2] = ++ cnt ;
        for (int i = 3 ; i <= n ; i += 2)
            yes[i] = yes[i + 1] = (cnt += 2) ;
        for (int i = 1 ; i <= n ; ++ i)
            if (base[i] != yes[i]) return printf("0\n"), 0 ;
    }
    return printf("%d\n", expow(2, n / 2)), 0 ;
}


Measured memory_bytes: 2688
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
using namespace std;


struct Node {
    int key;
    Node *right,*left,*parent;
};

Node *root,*NIL;

void insert(int k){
    Node *y = NIL;
    Node *x = root;
    Node *z;
    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->right = NIL;
    z->left = NIL;

    while( x!= NIL){
        y = x;
        if(x->key > z->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    z->parent = y;
    if(y == NIL){
        root = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}
void inorder(Node *u){
    if (u == NIL)return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}
void preorder(Node *u){
    if (u == NIL)return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}
int main(){
    int n,i,x;
    char com[100];
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        cin >> com;
        if(com[0] == 'i'){
            scanf("%d",&x);
            insert(x);
        }else if(com[0] == 'p'){
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }
    return 0;
}


Measured memory_bytes: 26592
#include<stdio.h>


int main(void){

  int x[100], a;
  int max=0;
  int size=0;
  int i;


  for(i=0; i<100; i++){
    x[i]=0;
  }

  while(scanf("%d", &a)!=EOF){
    if(size<a) size=a;

    x[a-1]++;
    if(max<x[a-1]) max=x[a-1];
  }

  for(i=0; i<size; i++){
    if(x[i]==max){
      printf("%d\n", i+1);
    }
  }

  return(0);
}



Measured memory_bytes: 2048
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

const int magic=1500;

char s[2111][10111];
int n,k,l[2111];
bool dp[2111][10111];
vector<pii> pos,npos;
int main()
{
	get2(n,k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s[i]+1);
		l[i]=strlen(s[i]+1);
	}
	
	dp[n+1][0]=1;
	for(int i=n;i>=1;i--)
	{
		for(int j=0;j<=k;j++)
		{
			dp[i][j]=dp[i+1][j];
			if(j>=l[i])dp[i][j]|=dp[i+1][j-l[i]];
		}
	}
	
	for(int i=1;i<=n;i++)if(dp[i+1][k-l[i]])pos.pb(mp(i,1));
	for(int _=1;_<=k;_++)
	{
		npos.clear();
		char cur='z';for(int i=0;i<(int)pos.size();i++)cur=min(cur,s[pos[i].ff][pos[i].ss]);
		putchar(cur);
		
		int mn=n;
		for(int i=0;i<(int)pos.size();i++)
		{
			if(s[pos[i].ff][pos[i].ss]!=cur)continue;
			if(l[pos[i].ff]==pos[i].ss)
				mn=min(mn,pos[i].ff);
			else npos.pb(mp(pos[i].ff,pos[i].ss+1));
		}
		for(int i=mn+1;i<=n;i++)if(_+l[i]<=k&&dp[i+1][k-_-l[i]])npos.pb(mp(i,1));
		
		if((int)npos.size()>magic)
		{
			random_shuffle(npos.begin(),npos.end());
			npos.resize(magic);
		}
		pos.swap(npos);
	}
	return 0;
}


Measured memory_bytes: 41344
#include <stdio.h>
int main() {
    int a,b,c,d,p,x,y;
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    scanf("%d",&d);
    scanf("%d",&p);
    x = p*a;
    if(c>p){
        y = b;
    }else if(c<p){
        y = b + (p-c)*d;
    }
    if(x>y){
        printf("%d\n", y);
    }else{
        printf("%d\n", x);
    }
    return 0;
}

Measured memory_bytes: 596
import sys


def input(): return sys.stdin.readline().rstrip()


n = int(input())
c = list(map(int, input().split()))
c = [x-1 for x in c]
# print(c)
adj = [[] for i in range(n)]
for i in range(n-1):
    a, b = tuple(map(int, input().split()))
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


size = [1 for i in range(n)]
stack = [[] for color in range(n)]
in_time = [-1 for i in range(n)]
out_time = [-1 for i in range(n)]
timer = 0
total = n*(n+1)//2
ans = [total for color in range(n)]
# print(ans)


def dfs(parent, root):
    global timer
    in_time[root] = timer
    timer += 1

    for child in adj[root]:
        if parent == child:
            continue
        dfs(root, child)
        size[root] += size[child]

        cnt = size[child]
        while stack[c[root]]:
            x = stack[c[root]][-1]
            if in_time[x] > in_time[root] and out_time[x] != -1:
                cnt -= size[x]
                stack[c[root]].pop()
            else:
                break
        ans[c[root]] -= cnt*(cnt+1)//2

    out_time[root] = timer
    timer += 1

    stack[c[root]].append(root)


sys.setrecursionlimit(10**6)

dfs(0, 0)
# print(size)
for color in range(n):
    cnt = n
    while len(stack[color]) > 0:
        x = stack[color][-1]
        cnt -= size[x]
        stack[color].pop()
    # print("node:", -1, "color:", color, "cnt:", cnt)
    ans[color] -= cnt*(cnt+1)//2
    print(ans[color])


Measured memory_bytes: 398396
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

int main (void) {

  int H, W; std::cin >> H >> W;
  int h, w; std::cin >> h >> w;

  std::cout << (H-h) * (W-w) << std::endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define eps (1e-10)
using namespace std;
class Point
{
	public:
	double x,y;
	Point(double _x=0,double _y=0):x(_x),y(_y){}
	Point operator + (Point p){ return Point(x+p.x,y+p.y);} 
	Point operator - (Point p){ return Point(x-p.x,y-p.y);}
	Point operator * (double a){return Point(a*x,a*y);} 
	Point operator / (double a){return Point(x/a,y/a);}
	double norm(){return x*x+y*y;}
	double ABS(){return sqrt(norm());} 
};
struct Segment
{
	Point p1,p2;	
};
//判断是否正交 向量内积：a*b=|a||b|*cos(Y) 当cos为0时正交(90,-90垂直) 
//a*b=a.x*b.x+a.y*b.y;
bool solve1(Point a,Point b)//是否正交 
{
	double f=a.x*b.x+a.y*b.y; 
	if(fabs(f-0.0)<eps) return true;
	else return false;
}
//判断是否平行  向量外积：|a*b|=|a||b|sin(Y) 当sin为0时平行(180,0平行)
//|a*b|=|a|*|b|*sin(Y) 
bool solve2(Point a,Point b)//是否平行 
{
	double f=a.x*b.y-a.y*b.x;
	if(fabs(f-0.0)<eps) return true;
	else return false;
}
double dot(Point a,Point b)
{
	return a.x*b.x+a.y*b.y;
}
/*
求垂足x：对于给定的三点p1,p2,p从点p向通过p1,p2的直线引一条垂线
base=p2-p1;
hypo=p-p1;
 x=s.p1+base*(hypo*base/|base|^2); hypo*base 可以用向量内积求 
*/
Point solve3(Segment s,Point p)//求投影点 
{
	Point base=s.p2-s.p1;
	double r=dot(p-s.p1,base)/base.norm();
	return s.p1+base*r; 
}
Point solve4(Segment s,Point p)
{
	return p+(solve3(s,p)-p)*2.0;
}
int main()
{
	double x1,y1,x2,y2;
	scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
	Point p1(x1,y1),p2(x2,y2);
	Segment s;
	s.p1=p1,s.p2=p2;
	int T;scanf("%d",&T);
	while(T--){
		double x,y;scanf("%lf %lf",&x,&y);
		Point p(x,y);
		Point w=solve4(s,p);
		printf("%.10f %.10f\n",w.x,w.y);
	}
	return 0;
}



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

#define name ""
#define ini freopen(name".inp","r",stdin); freopen(name".out","w",stdout)
#define foe(it,c) for (__typeof(c.begin()) it = c.begin(); it != c.end(); it++)
#define long long long 
#define db double 
#define pii pair <int, int>
#define pll pair <long, long>
#define all(c) c.begin(), c.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

const int INF = 1e9+7;
const int MOD = 1e9+7;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};

int main()
{
  fastio;
  int a, b, c, d; 
  cin >> a >> b >> c >> d;
  for (int i = 1; ; i++){
    if (i % 2) c -= b;
    else a -= d; 
    if (c <= 0) return cout << "Yes", 0;
    if (a <= 0) return cout << "No", 0;
  }
  return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define REP(i, a, n) for(int i=a; i<n; i++)
#define RREP(i, a, n) for(int i=n-1; i>=a; i--)
#define CK(n, a, b) (a <= n && n < b)
#define MP(a, b) make_pair(a, b)
typedef long long ll;
const ll mod =1e9+7;
const int inf =1e9;
using namespace std;

ll A, B, M;
ll a[101010], b[101010], x[101010], y[101010], c[101010];
int main() {
    cin>>A>>B>>M;
    REP(i, 0, A) cin>>a[i];
    REP(i, 0, B) cin>>b[i];
    REP(i, 0, M) cin>>x[i]>>y[i]>>c[i];

    ll mn=inf, mna=inf, mnb=inf;
    REP(i, 0, M){
        mn=min(mn, a[x[i]-1]+b[y[i]-1]-c[i]);
    }
    REP(i, 0, A) mna=min(mna, a[i]);
    REP(i, 0, B) mnb=min(mnb, b[i]);

    cout<<min(mn, mna+mnb)<<endl;
    return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
    ll N,K,S;
    cin >> N >> K >> S;

    for(ll i = 0; i<N ; i++){
        if(i < K){
            cout << S;
        }else if(S!=1000000000){
            cout << S+1;
        }else{
            cout << 1;
        }
        if(i != N-1)
            cout << ' ';
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define pf push_front
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define SZ(x) (int)(x).size()
#define endl '\n'
#define FOR(a, b, c) for (auto(a) = (b); (a) < (c); ++(a))
#define ROF(a, b, c) for (auto(a) = (b); (a) > (c); --(a))
#define F0R(a, b) FOR ((a), 0, (b))
#define R0F(a, b) ROF ((a), (b), -1)
#define CEIL(a, b) ((a) + (b)-1) / (b)
#define SET(a, b) memset((a), (b), sizeof(a))
template <class t>
bool ckmin(t& a, const t& b) {
    return a > b ? a = b, true : false;
}
template <class t>
bool ckmax(t& a, const t& b) {
    return a < b ? a = b, true : false;
}
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout \
    if (DEBUG) std::cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
template <class a, class b>
ostream& operator<<(ostream& o, const pair<a, b>& p);
template <class T>
struct IsC {
    template <class C>
    static char test(typename C::const_iterator*);
    template <class C>
    static int test(...);
    static const bool value = sizeof(test<T>(0)) == sizeof(char);
};
template <>
struct IsC<string> {
    static const bool value = false;
};
template <class C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(ostream& o,
                                                             const C& c) {
    o << '[';
    for (auto it = c.begin(); it != c.end();)
        o << *it << (++it != c.end() ? ", " : "");
    return o << ']';
}
template <class a, class b>
ostream& operator<<(ostream& o, const pair<a, b>& p) {
    return o << '(' << p.fi << ", " << p.se << ')';
}

const ll maxLeafs = 1e8;

void solve() {
    int n;
    cin >> n;
    vector<ll> as(n + 1);
    F0R (i, n + 1) cin >> as[i];
    if (as[0] == 1) {
	if (n == 0) {
	    cout << 1 << endl;
	} else {
	    cout << -1 << endl;
	}
	return;
    }
    if (as[0] > 1) {
	cout << -1 << endl;
	return;
    }
    vector<ll> low(n + 1, 1), high(n + 1, 1);
    FOR (i, 1, n + 1) {
	if (high[i - 1] * 2 < as[i]) {
	    cout << -1 << endl;
	    return;
	}
	high[i] = min(high[i - 1] * 2 - as[i], (n - i) * maxLeafs);
	low[i] = max(low[i] - as[i], 0ll);
	dout <<  dvar(low[i]) << dvar(high[i]) << endl;
    }
    if (low[n] > 0) {
	cout << -1 << endl;
	return;
    }
    ll cnt = 1 + as[n], nodes = as[n];
    
    for (int i = n - 1; i; --i) {
	nodes = min(nodes + as[i], high[i] + as[i]);
	cnt += nodes;
    }
    cout << cnt << endl;
}

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

    int tt = 1;
    FOR (t, 1, tt + 1) {
	// cout << "Case #" << t << ": ";
	solve();
    }

    return 0;
}


Measured memory_bytes: 5504
import sys

N, K = map(int, input().split())
lst = list(map(int, input().split()))

lst_p = []
lst_m = []
for i in range(N):
    if lst[i] == 0:
        K -= 1
    if lst[i] > 0:
        lst_p += [lst[i]]
    elif lst[i] < 0:
        lst_m += [lst[i]]


p = 0
m = 0
x, y = 0, len(lst_m)-1
lastx = len(lst_p)
lasty = len(lst_m)
#print (lastx, lasty)

def check(k):
    ans = 10 ** 9
    for j in range(0,k+1): #j: 正側の使う個数
#        print ('j, k-j', j, k-j)
        if j > lastx or k-j > lasty:
            pass
        else:
            if j == 0:
                p = 0
            else:
                p = lst_p[j-1]
            if k-j == 0:
                m = 0
            else:
                m = lst_m[lasty-(k-j)]
            ans = min(ans, 2 * p + abs(m), p + 2 * abs(m))
    return ans

print (check(K))

Measured memory_bytes: 14568
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int v,e;
int d[22][22];
int dp[1<<16];
int cnt[22];
int sum;
main()
{
	cin>>v>>e;
	for(int i=0;i<v;i++)for(int j=0;j<v;j++)if(i!=j)d[i][j]=1e9;
	for(int i=0;i<e;i++)
	{
		int s,t,D;cin>>s>>t>>D;d[s][t]=d[t][s]=min(d[s][t],D);
		cnt[s]++,cnt[t]++;
		sum+=D;
	}
	for(int k=0;k<v;k++)for(int i=0;i<v;i++)for(int j=0;j<v;j++)
		d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	for(int i=0;i<1<<v;i++)dp[i]=1e9;
	int zero=0;
	for(int i=0;i<v;i++)zero|=(cnt[i]%2<1)<<i;
	dp[zero]=0;
	for(int i=0;i<1<<v;i++)
	{
		for(int j=0;j<v;j++)
		{
			if(i&(1<<j))continue;
			for(int k=j+1;k<v;k++)
			{
				if(i&(1<<k))continue;
				dp[i|(1<<j)|(1<<k)]=min(dp[i|(1<<j)|(1<<k)],dp[i]+d[j][k]);
			}
		}
	}
	cout<<sum+dp[(1<<v)-1]<<endl;
}



Measured memory_bytes: 3220
#include <iostream>
#include <vector>
#include <cmath>
#define SIZE 10001
using namespace std;

int getNum(int x, int y, int z){
	return (x*x) + (y*y) + (z*z) + (x*y) + (y*z) + (z*x);
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	int sqrtn = sqrt(n);
	vector<int> num(n+1);
	for(int x=1; x<=sqrtn; x++){
		for(int y=1; y<=sqrtn; y++){
			for(int z=1; z<=sqrtn; z++){
				int val = getNum(x, y, z);
				if(val <= n){
					num[val]++;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<num[i]<<'\n';
	}
}

Measured memory_bytes: 3572
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        boolean flag = true;
        if (!(s.charAt(0) == t.charAt(2))) {
            flag = false;
        }
        if (!(s.charAt(1) == t.charAt(1))) {
            flag = false;
        }
        if (!(s.charAt(2) == t.charAt(0))) {
            flag = false;
        }
        System.out.println(flag ? "YES" : "NO");
    }
}

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

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

}

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

using namespace std;

typedef long long ll;

int main() {
    ll N,M; cin>>N>>M;
    
    vector<vector<ll>> jobs(M);
    for (int i=0;i<N;i++) {
        ll a,b; cin>>a>>b;
        if (a-1 < M) {
            jobs[a-1].push_back(b);
        }
    }

    priority_queue<ll> que;

    ll sum=0;
    for (int i=0;i<M;i++) {
        for (ll b : jobs[i]) {
            que.push(b);
        }

        if (!que.empty()) {
            sum += que.top();
            que.pop();
        }
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 5632
#include<iostream>

using namespace std;


int main(){
    
    int M_H,N;
    cin>>M_H>>N;
    
    int arr[N];
    int sum=0;
    
    for(int i=0;i<N;i++){
        cin>>arr[i];
        sum+=arr[i];
    }
    
    
    if(sum>=M_H) cout<<"Yes"<<"\n";
    else cout<<"No";
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
//const long double EPS = 1e-14;
const int INF = (1<<30)-1;
//const ll INF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
//template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main () {
  int n;
  cin >> n;
  vi x(n);
  rep(i,n) cin >> x[i];
  
  int ans = INF;
  rrep(p,100) {
    int tot = 0;
    rep(i,n) {
      tot += (x[i]-p)*(x[i]-p);
    }
    chmin(ans, tot);
  }
  cout << ans << endl;
  return 0;
}

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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main()
{
    int n;
    cin >> n;
    int t[n + 1], x[n + 1], y[n + 1];

    t[0] = 0, x[0] = 0, y[0] = 0;

    for (int i = 1; i <= n; i++)
        cin >> t[i] >> x[i] >> y[i];

    rep(i, n)
    {
        int d = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
        int time = t[i + 1] - t[i];
        if (!(time >= d && d % 2 == time % 2))
        {
            OP("No");
            return 0;
        }
    }
    OP("Yes");
    return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
	int n, k;
	char s[100001];
	cin >> n;
	cin >> k;
	cin >> s;
	int first = 0, last;
	int i;
	int now = 1;
	int range = 0;
	for (i = 0; i < n; i++)
	{
		s[i] -= '0';
	}
	for (i = 0; i < n; i++)
	{
		if (now != s[i])
		{
			if (now == 0)
			{
				range++;
				if (range == k)
				{
					break;
				}
			}
			now = s[i];
		}
	}
	now = 1;
	int max = i;
	if (max == n)
	{
		cout << max << endl;
		return 0;
	}
	for (last = i; last < n; last++)
	{
		if (now != s[last])
		{
			if (now == 1)
			{
				int fnow = 1;
				for (;; first++)
				{
					if (fnow != s[first])
					{
						fnow = s[first];
						if (fnow == 1)
						{
							break;
						}
					}
				}
			}
			else
			{
			}
			now = s[last];
		}
		if (last - first > max)
		{
			max = last - first;
		}

	}
	cout << (max+1) << endl;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=998244353;
const int siz=1e5;
const long inf=1e9;
int main(){
	int N,S; cin>>N>>S;
	int a;
	long dp[S+1] = {}; dp[0] = 1;
	rep(i,1,N+1){
		cin>>a;
		for(int j = S; j >= a; j--) dp[j] = (2 * dp[j] + dp[j-a]) % mod;
		rep(j,0,min(a,S+1)) (dp[j] *= 2) %= mod;
	}cout<<dp[S]<<endl;//print(dp,,S+1);
}

Measured memory_bytes: 3660
#include<bits/stdc++.h>
#define LL long long
#define MEM(x,y) memset(x,y,sizeof(x))
#define MOD(x) ((x)%mod)
#define mod 1000000007
#define pb push_back
#define STREAM_FAST ios::sync_with_stdio(false)
using namespace std;
const int maxn = 1e5 + 7;
int head[maxn];
struct node{int v, next, c, w;}e[maxn << 1];
LL ans[maxn];
struct Node
{
    int id, c, y, op;
    Node(int id, int c, int y, int op):id(id), c(c), y(y), op(op) {}
    Node() {}
};
vector<Node>Q[maxn];
int tot = 1;
void add(int u, int v, int c, int w)
{
    e[++tot] = {v, head[u], c, w};
    head[u] = tot;
}
int f[maxn][20], dep[maxn];
void dfs(int u, int fa)
{
    for (int i = 1; i <= 19; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if (v == fa) continue;
        dep[v] = dep[u] + 1; f[v][0] = u;
        dfs(v, u);
    }
}
int LCA(int x, int y)
{
    if (dep[x] > dep[y]) swap(x, y);
    for (int i = 19; i >= 0; i--) if (dep[y] > dep[x] && dep[f[y][i]] >= dep[x]) y = f[y][i];
    for (int i = 19; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return x == y ? x : f[x][0];
}

int cnt[maxn], sum[maxn], dis = 0;
void DFS(int u, int fa)
{
    for (Node qy : Q[u])
    {
        ans[qy.id] += qy.op * (dis - sum[qy.c] + cnt[qy.c] * qy.y);
    }
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if (v == fa) continue;
        cnt[e[i].c]++; sum[e[i].c] += e[i].w;
        dis += e[i].w;
        DFS(v, u);
        cnt[e[i].c]--; sum[e[i].c] -= e[i].w;
        dis -= e[i].w;
    }
}
int main()
{
	int n, q; scanf("%d%d", &n, &q);
    for (int i = 1; i < n; i++)
    {
        int u, v, c, d; scanf("%d%d%d%d", &u, &v, &c, &d);
        add(u, v, c, d); add(v, u, c, d);
    }
    dep[1] = 1;
    dfs(1, -1);
    for (int i = 1; i <= q; i++)
    {
        int u, v, x, y; scanf("%d%d%d%d", &x, &y, &u, &v);
        int lca = LCA(u, v);
        Q[u].pb(Node(i, x, y, 1));
        Q[v].pb(Node(i, x, y, 1));
        Q[lca].pb(Node(i, x, y, -2));
    }
    DFS(1, -1);
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
	return 0;
}


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

int64_t jyo(int64_t x,int64_t y,int64_t z){
  int64_t H=y; //ここから
       int64_t a=1,b=x,c=1;
       while(H>0){
         a*=2;
         if(H%a!=0){
           H-=a/2;
           c*=b;
           c%=z;
         }
        b*=b;
         b%=z;
      } //ここまで
 return c;
}

int64_t Q=998244353;
  

int main(){
  vector<int64_t> p={1};
  int N,S=1;
  cin>>N;
  map<int,int64_t> m;
  for(int i=0;i<N*2;i++){
    int a;
    cin>>a;
    m[a]++;
  }
  vector<vector<int64_t>> r;
  r.push_back(p);
  for(auto x:m){
    S++;
    int64_t A=x.second;
    int64_t B=1;
    vector<int64_t> q={1};
    int64_t K=1;
    while(A>1){
      K*=A;
      K%=Q;
      A--;
      K*=A;
      K%=Q;
      A--;
      K*=(Q+1)/2;
      K%=Q;
      K*=jyo(B,Q-2,Q);
      K%=Q;
      B++;
      q.push_back(K);
    }
    r.push_back(q);
  }
  priority_queue<int64_t> pq;
  for(int i=0;i<S;i++){
    int64_t m=r[i].size();
    pq.push(m*-1*Q-i);
  }
  for(int j=1;j<S;j++){
    int64_t a,b;
    a=pq.top();
    pq.pop();
    b=pq.top();
    pq.pop();
    a=abs(a);
    b=abs(b);
    int64_t l=a/Q+b/Q-1;
    a%=Q,b%=Q;
    r[a]=convolution<998244353>(r[a],r[b]);
    pq.push(-1*l*Q-a);
  }
  p=r[abs(pq.top())%Q];
  int L=p.size();
  int64_t Z=0,A=1,a=-1,M=N;
  for(int64_t i=N+1;i<=2*N;i++){
    A*=i;
    A%=Q;
  }
  A*=jyo(jyo(2,N,Q),Q-2,Q);
  A%=Q;
  for(int i=0;i<L;i++){
    a*=-1;
    int64_t D=(p[i]*A)%Q;
    Z+=((Q+D*a)%Q);
    Z%=Q;
    A*=2;
    A*=M;
    A%=Q;
    int64_t E=(2*M*(2*M-1))%Q;
    A*=jyo(E,Q-2,Q);
    A%=Q;
    M--;
  }
  cout<<Z<<endl;
}

Measured memory_bytes: 16468
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < n;i++)
#define ll long long
#include <bits/stdc++.h>
using namespace std;
#define mo 1000000007
#define ull unsigned long long 

int main(){
  ll n;cin>>n;
  vector<ll>l(n+1);
  l.at(0)=2;
  l.at(1)=1;
  for(int i=2;i<n+1;i++)
  {
    l.at(i)=l.at(i-1)+l.at(i-2);
  }
  cout<<l.at(n);
}
    


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define M 1000000007 
#define MM 998244353
#define PI 3.14159265 
using namespace std;

int main()
{
	int n;

	cin >> n;

	vector<vector<int> > v( n , vector<int> (3));
	vector<vector<int> > dp( n , vector<int> (3));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> v[i][j];
			dp[i][j] = 0;
		}
	}

	for (int i = 0 ; i < 3; i++)
	{
		dp[0][i] = v[0][i];
	} 

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (j == 0)
			{
				dp[i][j] = max(dp[i-1][1], dp[i-1][2]) + v[i][j];
			}
			else if (j == 1)
			{
				dp[i][j] = max(dp[i-1][0], dp[i-1][2]) + v[i][j];
			}
			else if (j == 2)
			{
				dp[i][j] = max(dp[i-1][0], dp[i-1][1]) + v[i][j];
			}
		}
	}

	int ans = max(dp[n-1][0], dp[n-1][1]);
	ans = max (ans, dp[n-1][2]);
	cout << ans;

  	return 0;
}

Measured memory_bytes: 13980
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)

template<int um> class UF {
public:
	vector<int> par, rank;
	UF() { rank = vector<int>(um, 0); for (int i = 0; i<um; i++) par.push_back(i); }
	int operator[](int x) { return (par[x] == x) ? (x) : (par[x] = operator[](par[x])); }
	int operator()(int x, int y) {
		if ((x = operator[](x)) == (y = operator[](y))) return x;
		if (rank[x]>rank[y]) return par[x] = y;
		rank[x] += rank[x] == rank[y]; return par[y] = x;
	}
};

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

	while (1)
	{
		int n, m; cin >> n >> m;
		if (n == 0) return 0;
		
		vector< pair<int, int> > E;
		rep(i, 0, m)
		{
			int s, t, c;
			cin >> s >> t >> c;
			s--;
			t--;
			E.push_back(make_pair(c, s * 1000 + t));
		}

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

		UF<1010> uf;
		vector<int> costs;
		int cnt = 0;

		for (auto p : E)
		{
			int s = p.second / 1000;
			int t = p.second % 1000;
			int c = p.first;

			if (uf[s] == uf[t]) continue;
			
			uf(s, t);
			costs.push_back(c);
			cnt++;

			if (cnt == n - 1) break;
		}

		sort(costs.begin(), costs.end());
		cout << costs[n / 2 - 1] << endl;
	}
}

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

int main(){
    int a;
    int b;
    int c ; 
    cin >> a >> b >> c;
    if(a<b && a<c && b<c){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

    return 0;
}


Measured memory_bytes: 3020
from collections import deque
n = int(input())
ki = [[] for i in range(n)]
d = [0 for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x: int(x)-1,input().split())
    ki[a].append(b)
    ki[b].append(a)
c = list(map(int,input().split()))
c.sort(reverse=True)
c = deque(c)
ans = 0
d[0] = c.popleft()
q = deque()
q.append(0)
while q:
    now = q.popleft()
    for i in ki[now]:
        if d[i] == 0:
            d[i] = c.popleft()
            q.append(i)
            ans += d[i]
print(ans)
print(*d)

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

// 0-indexed
template <class T>
struct BIT {
  int treesize;
  vector<T> lst;
  // constructor
  BIT(int newn = 0) : treesize(newn), lst(newn + 1, 0) {}
  // a_place += num
  void add(int place, T num) {
    ++place;
    while (place <= treesize) {
      lst[place] += num;
      place += place & -place;
    }
  }
  // sum between [0,place)
  T sum(int place) {
    T res = 0;
    while (place > 0) {
      res += lst[place];
      place -= place & -place;
    }
    return res;
  }
  // sum [l,r)
  T sum(int left, int right) { return sum(right) - sum(left); }
};

struct EulerTour {
  int n, root;
  vector<vector<int>> g;
  vector<int> par, dep, in, out, lst;
  EulerTour(int n = 1, int _root = 0)
      : root(_root), g(n), par(n), dep(n), in(n), out(n) {}
  EulerTour(const vector<vector<int>> &_g, const int _root = 0)
      : root(_root),
        g(_g),
        par(_g.size()),
        dep(_g.size()),
        in(_g.size()),
        out(_g.size()) {
    build();
  }
  void add(int a, int b) {
    g[a].push_back(b);
    g[b].push_back(a);
  }
  void build() {
    lst.clear();
    dfs(root, -1, 0);
  }
  void dfs(int now, int bf, int d) {
    dep[now] = d;
    par[now] = bf;
    in[now] = lst.size();
    lst.push_back(now);
    for (auto &to : g[now])
      if (to != bf) {
        dfs(to, now, d + 1);
        lst.push_back(now);
      }
    if (lst.back() != now) lst.push_back(now);
    out[now] = lst.size();
  }
  int chil(int x, int y) { return dep[x] < dep[y] ? y : x; }
};


long long n;
vector<int> c;
vector<vector<int>> edge, col, memo;

void solve();

int main() {
  cin >> n;
  c.resize(n);
  edge.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> c[i];
    --c[i];
  }
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  solve();
  return 0;
}

void solve() {
  EulerTour et(edge);
  BIT<long long> bit(et.lst.size());
  col.resize(n);
  memo.resize(n);
  for (int i = 0; i < n; ++i) bit.add(et.in[i], 1);
  for (int i = 0; i < et.lst.size(); ++i) memo[et.lst[i]].push_back(i);
  for (int i = 0; i < n; ++i) col[c[i]].push_back(i);
  for (int i = 0; i < n; ++i) {
    long long res = n * (n + 1) / 2;
    using P = pair<int, int>;
    vector<P> v;
    map<int, int> mp;
    for (int node : col[i]) {
      bit.add(et.in[node], -1);
      mp[node] = 1;
      for (int id = 0; id < (int)memo[node].size() - 1; ++id)
        v.emplace_back(memo[node][id + 1], node);
    }
    sort(v.begin(), v.end());
    for (P p : v) {
      long long now = bit.sum(et.in[p.second], p.first);
      res -= now * (now + 1) / 2;
      mp[p.second] += now;
      bit.add(et.in[p.second], -now);
    }
    long long last = bit.sum(et.lst.size());
    res -= last * (last + 1) / 2;
    cout << res << endl;
    for (auto p : mp) bit.add(et.in[p.first], p.second);
  }
}


Measured memory_bytes: 70104
#include <iostream>
#include <string>
using namespace std;
int main(void){
    string A;
    int m,h=0;
    while(cin>>A){
        if(A=="-") break;
        cin>>m;
        for(int i = 0; i < m ; i++){
            cin>>h;
            A = A.substr(h)+A.substr(0,h);
        }
        cout<<A<<endl;
    }
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

ll N;

vector<pii> e[100001];
int node_color[100001];

// 点0からの距離が偶数か奇数かで色を塗る
void dfs( int node, int parent_node, int color ){
	node_color[node] = color;
	for ( auto it : e[node] ){
		int next_node = it.first;
		if ( next_node == parent_node )
			continue;
		dfs( next_node, node, (color + it.second) % 2 );
	}
}

int main(){
	cin >> N;
	
	for ( int i = 0; i < N-1; i++ ){
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;
		w = w%2;
		
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	
	dfs( 0, -1, 0 ); 
	
	for ( int i = 0; i < N; i++ )
		cout << node_color[i] << "\n";
	
	return 0;
}



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

int main() {
  int N;
  cin >> N;
  int ans = 0;
  
  for (int i=0; i < N; i ++){
    int A;
    cin >> A;
    int d_num = 0;
    for(int j =0; ;j ++){
      if (A % 2 == 0){
        d_num ++;
        A = A/2;
      }
      
      else
        break;
    }
    
    if (i == 0)
      ans = d_num;
    if (ans > d_num)
      ans = d_num;
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int a,b,total=0,s=0,i;
    cin>>a>>b;
    for (i=a;i<=b;i++)
    {
        int p=i;
        s=0;
        while (p!=0)
        {
            s=s*10+p%10;
            p=p/10;
        }
        if (s==i)  total++;
    }
    cout<<total<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
int main(){
  string s;cin >> s;
  int ans = 0,now = 0,i;
  for(i=0;i<3;i++){
    if(s[i] == 'R') now++;
    else now = 0;
    ans = max(ans,now);
  }
  cout << ans << "\n";
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> L(M), R(M);
  for (int i = 0; i < M; i++) cin >> L.at(i) >> R.at(i);
  sort(L.begin(), L.end());
  sort(R.begin(), R.end());
  if (R.at(0) - L.at(M-1) + 1 > 0) cout << R.at(0) - L.at(M-1) + 1 << endl;
  else cout << 0 << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long int
#define double /*long*/ double
#define endl '\n'
#define vll vector<ll>
#define vvl vector<vll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vppll vector<pll,pll>
#define mp make_pair
#define pb push_back
#define mapll map<ll,ll>
#define fir first
#define sec second
#define _cin ios_base::sync_with_stdio(0);  cin.tie(0);
#define fo(i,b) for(i=0;i<b;i++)
#define repa(i,a,b) for(i=a;i<b;i++)
#define repb(i,a,b) for(i=a;i>=b;i--)
#define all(x) (x).begin(), (x).end()
#define s(v) (ll)v.size()
#define watch(x) cerr << (#x) << " is " << (x) << endl
#define Time cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n"
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
const long long int MAX = (ll)(1e18+1);
const long long int MIN = (ll)(-1e18-1);
const long long int mod = (ll)(1e9+7);
using namespace std;  // order_of_key(k) -> Number of elements strictly smaller than k
using namespace __gnu_pbds; // order_of_key() ; *( find_by_order() ) -> kth element in set;

ll max(ll a,ll b,ll c) {return max(max(a, b), c);}
ll min( ll a, ll b, ll c) { return min(min(a, b), c);}
ll max(ll a,ll b) {return (a>b) ? a : b;}
ll min(ll a,ll b) {return (a<b) ? a : b;}
ll power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll power_mod(ll a, ll n, ll mod_){ ll p=1; while(n){ if(n%2){ p=(p*a)%mod_;} n/=2; a=(a*a)%mod_;} return p%mod_;}                 
                          /*Code Begins*/




int main(){
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    _cin;
    // cout << setprecision(15);
    ll mn = MAX, mx = MIN;
    ll n, m, t,  k, i, j,  sum=0,  prev, flag=0, cnt=0;
    ll x=0, y=0, fx, diff, tot=0, l , r;
    int TC=1;
    // cin >> TC;
while(TC--){
    cin >> m >> n;
    sum=0;
    fo(i,n) cin >> x, sum+=x;
    x = m-sum;
    if(x<0) x=-1;
    cout << x ;
    
    
    
}

    Time;
    return 0;
}


Measured memory_bytes: 3812
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define llong long long int
#define ullong unsigned long long int
const static long long int MOD = 1000000000 + 7;

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;

    llong I[n + 1];
    for (int i = 1; i <= n; ++i) {
        int a;
        cin >> a;
        I[a] = i;
    }

    llong ans = 0;
    set<llong> check = {0, n + 1};
    for (int i = 1; i <= n; ++i) {
        int left, right;
        set<llong>::iterator itr = check.lower_bound(I[i]);
        right = *itr;
        left = *(--itr);

        ans += i * (I[i] - left) * (right - I[i]);
        check.insert(I[i]);
    }

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

Measured memory_bytes: 11264