akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node{
  int p, l, r;
};

struct Node T[MAX];
int n;
int D[MAX], H[MAX];

int getDepth(int u){
  int d = 0;
  while(1){
    u = T[u].p;
    if ( u == NIL ) break;
    d++;
  }
  return d;
}

int getSibling(int u){
  if ( T[u].p == NIL ) return NIL;
  if ( T[T[u].p].l != u && T[T[u].p].l != NIL ) return T[T[u].p].l;
  if ( T[T[u].p].r != u && T[T[u].p].r != NIL ) return T[T[u].p].r;
  return NIL;
}

void print(int u){
  printf("node %d: ", u);

  printf("parent = %d, ", T[u].p);
  printf("sibling = %d, ", getSibling(u));
  int deg = 0;
  if ( T[u].l != NIL ) deg++;
  if ( T[u].r != NIL ) deg++;
  printf("degree = %d, ", deg);
  printf("depth = %d, ", D[u]);
  printf("height = %d, ", H[u]);

  if ( T[u].p == NIL ){
    printf("root\n");
  } else if ( T[u].l == NIL && T[u].r == NIL ){
    printf("leaf\n");
  } else {
    printf("internal node\n");
  }
}

main(){
  int i, v, l, r;
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ) {
    T[i].p = NIL;
  }

  for ( i = 0; i < n; i++ ){
    scanf("%d %d %d", &v, &l, &r);
    T[v].l = l;
    T[v].r = r;
    if ( l != NIL ) T[l].p = v;
    if ( r != NIL ) T[r].p = v;
  }

  for ( i = 0; i < n; i++ ){
    D[i] = getDepth(i);
    H[i] = 0;
  }

  for ( i = 0; i < n; i++ ){
    if ( T[i].l == NIL && T[i].r == NIL ) { // is leaf
      H[i] = 0;
      int p = T[i].p;
      int c = 1;
      while(1){
	if ( p == NIL ) break;
	if ( H[p] < c ) H[p] = c;
	c++;
	p = T[p].p;
      }
    }
  }

  for ( i = 0; i < n; i++ ) print(i);
  return 0;
}



Measured memory_bytes: 2048
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>

using namespace std;
int a[100005], qian[100005], hou[100005];

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

int Max(int a, int b){
    return a>b?a:b;
}

int main()
{
    int n,i,j;
    cin>>n;
    for(i=0;i<n;i++) cin>>a[i];
    qian[0]=a[0];
    hou[n-1]=a[n - 1];
    for (i=1;i<n;i++) qian[i]=gcd(qian[i-1],a[i]);
    for (i=n-2;i>=0;i--) hou[i]=gcd(hou[i+1],a[i]);
    int max=qian[n-1];
    for (i=0;i<n;i++){
        if(i==0) max=Max(max,hou[1]);
        else if(i==n-1) max=Max(max,qian[n-2]);
        else max=Max(max,gcd(qian[i-1],hou[i+1]));
    }
    cout<<max<<endl;
    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const ll N = 3005;
const ll base = 313;
const ll base1 = 113;
const ll mod = 1e9 + 7;
ll n, t, pr[N], nx[N], T, k, b[N], c[N][N], dp[N][N][4], sum= 0, m, tong, ans, pw1[N], pw[N];
struct dang
{
    ll l, r, pos;
};
ll a[N];
string s;
vector<ll> kq;
void sol()
{
    cin >> n >> m >> k;
    ans = -mod;
    for(int i = 1; i <= k; i ++)
    {
        ll x, y, w;
        cin >> x >> y >> w;
        c[x][y] = w;
    }
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            t = max(max(max(dp[i-1][j][0], dp[i-1][j][1]), dp[i-1][j][2]), dp[i-1][j][3]);
            dp[i][j][0] = max(t, dp[i][j-1][0]);
            dp[i][j][1] = max(t + c[i][j], max(dp[i][j-1][0] + c[i][j], dp[i][j-1][1]));
            dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + c[i][j]);
            dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + c[i][j]);
        }
    }
    //cout << dp[2][3][1] <<" ";
    cout << max(dp[n][m][0], max(dp[n][m][1], max(dp[n][m][2], dp[n][m][3])));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    sol();
}


Measured memory_bytes: 355752
import java.util.Scanner;

public class Main {
	@SuppressWarnings("resource")
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int t=scanner.nextInt();
		int a=scanner.nextInt();
		int h[]=new int[n];
		for(int i=0;i<n;i++) {
			h[i]=scanner.nextInt();
		}
		double min=Integer.MAX_VALUE;
		int ans=0;
		for(int i=0;i<n;i++) {
			double d=t-h[i]*0.006;
			double p=Math.abs(d-a);
			if(p<min) {
				min=p;
				ans=i;
			}
			
		}
		System.out.println(ans+1);
	}
}

Measured memory_bytes: 22484
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <utility>
#include <algorithm>

int main() {
    long long n, m, a, b;
    std::cin >> n >> m;
    std::vector<std::deque<long long>> g(n);
    for (auto i = 0; i < m; i++) {
        std::cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    std::vector<bool> done(n, false);
    done[0] = true;
    std::set<long long> odd, even;
    even.insert(0);
    std::deque<std::pair<long long, bool>> q;
    for (auto to : g[0]) q.push_back({ to, true });
    while (!q.empty()) {
        auto curr = q.front();
        //std::cout << curr.first << std::endl;
        q.erase(q.begin());
        if (curr.second) odd.insert(curr.first);
        else even.insert(curr.first);
        
        if (done[curr.first]) continue;
        done[curr.first] = true;
        for (auto to : g[curr.first]) q.push_back({ to, !curr.second });
    }

    for (auto i : odd) {
        if (even.count(i) > 0) {
            std::cout << n * (n - 1) / 2 - m << std::endl;
            return 0;
        }
    }

    std::cout << odd.size() * even.size() - m << std::endl;

    return 0;
}

Measured memory_bytes: 72192
#include<bits/stdc++.h>
        #define ll long long int
        using namespace std;
        #define mod 1000000007
        #define pb push_back
        #define fi first
        #define si second
        #define mp make_pair
        #define f(n) for(ll i=0;i<n;i++)
        #define ff(m) for(ll j=0;j<m;j++)
        #define fr(i,p,n) for(ll i=p;i<n;i++)
        #define in insert
        ll exp(ll a,ll b,ll m);
        #define vl vector<ll> 
        #define pll pair <ll,ll>

    
        void solve(){

        	int n,W;
        	cin>>n>>W;

        	vl v(n+1,0);
        	vl w(n+1,0);

        	fr(i,1,n+1){
        		cin>>w[i]>>v[i];
        	}
        	ll	 dp[n+1][W+1];
        	memset(dp,0,sizeof(dp));

        	fr(i,1,n+1){
        		fr(j,1,W+1){
        			if(j<w[i])
        				dp[i][j]=dp[i-1][j];
        			else
        				dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]);
        		}
        	}


        	//dp(i,j)=max(dp(i-1,j),v[i]+dp(i-1,j-w[i]))
        	cout<<dp[n][W]<<endl;


        }
 
       int main(){
            
 
            int t=1;
 			//cin>>t;
            while(t--)
               solve();
    
    		return 0;
		}
 
		ll exp(ll a,ll b,ll m)
		{
			if(b==0)
			{
				return 1;
			}
			ll temp =exp(a,b/2,m);
			temp=(temp*temp)%m;
			if(b&1)
			{
				return (temp*(a%m))%m;
			}
			return temp;
		}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
using namespace std;
long long s=0;
int main()
{
	priority_queue <int> a;
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a.push(x);
	}
	for(int i=1;i<=m;i++){
		int y=a.top();
		y=y/2;
		a.pop();
		a.push(y);
	}
	for(int i=1;i<=n;i++){
		int y=a.top();
		s=s+y;
		a.pop();
	}
		
	printf("%lld\n",s);
}

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

using namespace std;

//State
//dp[i][j]: The number of ways to reach the cell (i,j) from (1,1)

//Initialization
//dp[1,1] = 1

//Transitions
//if A[i-1][j]== . and A[i][j-1]== . then dp[i][j] = dp[i-1][j]+dp[i][j-1]

//Order of evaluation
//Rowwise or Columnwise

//Answer
//dp[H-1][W-1]

//Time Complexity: O(H*W)

const int mod = 1e9+7;

int main(){
	int H, W;
	cin >> H >> W;
	vector<vector<int>> dp(H, vector<int>(W,0));
	vector<vector<char>> A(H, vector<char>(W));

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			cin >> A[i][j];
		}
	}
	
	dp[0][0] = 1;
    
    for(int i=1; i<H; i++){
        if(A[i][0]=='#') dp[i][0] = 0;
        else dp[i][0] = dp[i-1][0];
    }
    
    for(int i=1; i<W; i++){
        if(A[0][i]=='#') dp[0][i] = 0;
        else dp[0][i] = dp[0][i-1];
    }
    
	for(int i=1; i<H; i++){
		for(int j=1; j<W; j++){
		    if(A[i][j] == '#') dp[i][j] = 0;
		    else{
		        if(A[i-1][j]=='.' && A[i][j-1]=='.'){
			    	dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod;
		    	}
			    else if(A[i-1][j]=='#' && A[i][j-1]=='.'){
				    dp[i][j] = dp[i][j-1];
		        }
			    else if(A[i-1][j]=='.' && A[i][j-1]=='#'){
			    	dp[i][j] = dp[i-1][j];
			    }
			    else{
				    dp[i][j] = 0;
			    }   
		    }
		}
	}
	
	cout << dp[H-1][W-1] << endl;
}





Measured memory_bytes: 8492
N,M,X,Y=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
mx=max(x)
my=min(y)
if mx>my or X>Y:
    print("War")
    exit(0)
for z in range(mx+1,my+1):
    if X<z<=Y:
        print("No War")
        exit(0)
print("War")

Measured memory_bytes: 3064
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let a: u64 = sc.read();
    let b: u64 = sc.read();
    let c: u64 = sc.read();

    if a + b >= c {
        println!("No");
        return;
    }

    let d = c - a - b;
    if d * d > 4 * a * b {
        println!("Yes");
    } else {
        println!("No");
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
#define fi first
#define sc second
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;

int w, h;
P as, ae, bs, be;
string a[50], b[50];
bool use[50][50][50][50];
int daw[4] = {1,0,-1,0},dah[4]={0,1,0,-1};
int dbw[4] = {-1,0,1,0},dbh[4]={0,1,0,-1};

void solve(int pp, int qq, int rr, int ss){
	queue<PP> que;
	que.push(PP(P(pp,qq),P(rr,ss)));
	while(!que.empty()){
		PP qu = que.front(); que.pop();
		int p = qu.fi.fi, q = qu.fi.sc, r = qu.sc.fi, s = qu.sc.sc;
		rep(i,4){
			int dp = p+dah[i],dq = q+daw[i];
			int dr = r+dbh[i],ds = s+dbw[i];
			if(0>dp||dp>=h||0>dq||dq>=w||a[dp][dq]=='#'){
				dp = p;
				dq = q;
			}
			if(0>dr||dr>=h||0>ds||ds>=w||b[dr][ds]=='#'){
				dr = r;
				ds = s;
			}
			if(use[dp][dq][dr][ds]) continue;
			if(ae == P(dp,dq) && be != P(dr,ds)) continue;
			if(ae != P(dp,dq) && be == P(dr,ds)) continue;
			use[dp][dq][dr][ds] = true;
			que.push(PP(P(dp,dq),P(dr,ds)));
		}
	}
}

int main(){
	while(scanf("%d%d",&w,&h),w||h){
		memset(use,0,sizeof(use));
		rep(i,h) cin >> a[i] >> b[i];
		rep(i,h){
			rep(j,w){
				if(a[i][j] == 'L') as = P(i,j);
				if(b[i][j] == 'R') bs = P(i,j);
				if(a[i][j] == '%') ae = P(i,j);
				if(b[i][j] == '%') be = P(i,j);
			}
		}
		int d = 0;
		use[as.fi][as.sc][bs.fi][bs.sc] = true;
		solve(as.fi,as.sc,bs.fi,bs.sc);
		if(use[ae.fi][ae.sc][be.fi][be.sc]) puts("Yes");
		else puts("No");
	}
}

Measured memory_bytes: 8268
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        long[] a = new long[m];
        long[] d = new long[m];
        int[] g = new int[n];
        HashMap<Long,Integer> b = new HashMap<Long, Integer>();
        HashMap<Long, String> c  = new HashMap<Long, String>();

        for (int i=0;i<m;i++){
            int p = scan.nextInt();
            long y = scan.nextLong();
            b.put(y,p);
            a[i] = y;
            d[i] = y;
        }

        Arrays.sort(a);

        for (int j=0;j<m;j++){
            int p1 = b.get(a[j]);
            int p2 = g[p1-1]+1;
            g[p1-1] += 1;
            String a1 = "";
            String a2 = p1+"";
            String a3 = p2+"";
            for (int k1=0;k1<6-a2.length();k1++){
                a1 += "0";
            }
            a1 += a2;
            for (int k2=0;k2<6-a3.length();k2++){
                a1 += "0";
            }
            a1 += a3;
            c.put(a[j], a1);
        }

        for (int q = 0 ; q<m;q++){
            System.out.println(c.get(d[q]));
        }
    }
}

Measured memory_bytes: 91076
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

const int INF = 10000000;

int main(int argc, char *argv[])
{
  int N, a[300000], b[300000];
  string S;
  cin >> N;
  cin >> S;


  a[0] = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == '#') {
      a[i+1] = a[i] + 1;
    } else {
      a[i+1] = a[i];
    }
  }

  b[N] = 0;
  for (int i = N-1; i >= 0; i--) {
    if (S[i] == '.') {
      b[i] = b[i + 1] + 1;
    } else {
      b[i] = b[i + 1];
    }
  }


  int ans = N + 1;
  for (int i = 0; i <= N; i++) {
    ans = min(ans, a[i] + b[i]);
  }

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


Measured memory_bytes: 2692
import Data.List
import Data.Array
getInts = do
    x <- getLine
    let y = map (read::String->Integer) (words x) 
    return y


change [] n = []
change s n = 
    if isPrefixOf "AC" s then 
        [n] ++ change (tail s) (n + 1)
    else 
        [n] ++ change (tail s) n

solve' x q = do
    [a,b] <- getInts
    print $ (x ! (b-1)) - (x ! (a-1))
    if q > 1 then solve' x (q-1)
    else return ()

solve s n q = 
    solve' (listArray (0,n) (change s 0)) q

main::IO()
main=do
    [n,q] <- getInts
    s <- getLine
    solve s n q


Measured memory_bytes: 8060
n=int(input())
a=[int(input())for _ in range(n)]
a=a[::-1]
cnt=0
ans=0
for i in range(n):
	if cnt==0:
		if a[i]!=0:
			cnt=a[i]
			ans+=a[i]
	else:
		cnt-=1
		if a[i]>cnt:
			cnt=a[i]
			ans+=a[i]
		elif a[i]<cnt:
			print(-1)
			exit()
if cnt:
	print(-1)
	exit()
print(ans)

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

int main(){
  string s,t,a,b;
  int n;
  
  cin >> s;
  n = s.size();
  t = s;
  reverse(t.begin(), t.end());
  a = s.substr(0,(n-1)/2);
  b = a;
  reverse(b.begin(), b.end());
  if (s ==t && a == b) cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

#define MAX 1000

signed main() {
    ll H, W, h, w;
    cin >> H >> W >> h >> w;
    ll a[H][W];
    fill(a[0], a[H], MAX);
    rep(i, H) {
        rep(j, W) {
            if ((i - (h - 1)) % h == 0 && (j - (w - 1)) % w == 0)
                a[i][j] = - MAX * (h * w - 1) - 1;
        }
    }
    ll sum = 0;
    rep(i, H) {
        rep(j, W) {
            sum += a[i][j];
        }
    }
    if(sum <= 0){
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    rep(i, H) {
        rep(j, W) {
            if(j) cout << " ";
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3584
n,m,x = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
ans = 10**9
for i in range(2 ** n):
  skill = [0] * m
  overTen = False
  money = 0
  for j in range(n):
    if ((int(bin(i)[2:]) >> j) & 1):
      money += a[j][0]
      for h in range(m):
        skill[h] += a[j][h+1]
  for k in skill:
    if k >= x:
      overTen = True
    else:
      overTen = False
      break
  if overTen == True:
    if money < ans:
      ans = money

if ans == 10**9:
  print(-1)
else:
  print(ans)

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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 10000000000000007ll;

const double eps = 1e-10;

// del

const i64 MAXN = 100005;

i64 a, b;


int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    cin >> a >> b;

    cout << max(0ll, a - 2 * b);


    return 0;
}

Measured memory_bytes: 256
D = int(input())
c = list(map(int, input().split()))
s = []
for i in range(D):
    s.append(list(map(int, input().split())))
t = []
for i in range(D):
    t.append(int(input()))

a = [0]*26
total = 0
for i in range(D):
    ts = t[i]

    a[ts-1] = i+1
    cs = sum([x * (i+1 - y) for x, y in zip(c, a)])

    total = total + s[i][ts-1] - cs
    print(total)

Measured memory_bytes: 68584
public class Main {
  private static void solve() {
    int n = ni();
    int[] a = new int[n];
    int[] b = new int[n];
    long total = 0;
    int min = Integer.MAX_VALUE;
    boolean same = true;
    for (int i = 0; i < n; i ++) {
      a[i] = ni();
      b[i] = ni();
      total += a[i];
      if (a[i] != b[i]) same = false;
      if (a[i] > b[i]) {
        min = Math.min(b[i], min);
      }
    }
    
    if (same) {
      System.out.println(0);
    } else {
      System.out.println(total - min);
    }
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}




Measured memory_bytes: 30952
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)

def main():
    input()
    s=input()
    t=s
    while "()"in s:
        s=s.replace("()","")
    n,m=s.count(")"),s.count("(")
    s=n*"("+t+m*")"
    print(s)
if __name__ == '__main__':
    main()


Measured memory_bytes: 5056
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (ll)(1E9+7)
#define PI 3.1415926535897932384

template <class T>ostream &operator<<(std::ostream &o, const vector<T> &v)
{
	rep(i, v.size()) {
		o << (i > 0 ? " " : "") << v[i];
	}
	return o;
}



int main() {
	int d, g;
	cin >> d >> g;
	vector<int> p(d, 0);
	vector<int> c(d, 0);

	for (int i = 0; i < d; i++) {
		cin >> p[i] >> c[i];
	}

	int count = 0;
	int num = 0;
	int ma;
	int ans = INF;

	for (int i = 0; i < (1 << d); i++) {
		for (int j = 0; j < d; j++) {
			if ((i >> j) & 1) {
				num += (j + 1) * 100*p[j]+c[j];
				count+=p[j];
			}
			else {
				ma = j;
			}
		}
		if (g > num) {
			int ne = (g - num + ((ma+1) * 100) - 1) / ((ma+1) * 100);
			if (ne >= p[ma]) {
				num = 0;
				count = 0;
				continue;
			}
			else {
				count += ne;
			}
		}

		ans = min(ans, count);
		//cout << bitset<32>(i).to_string() << " " << count << endl;
		num = 0;
		count = 0;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
s = [int(i) for i in input().split()]

f5 = 2
f7 = 1

for i in s:
    if(i == 5):
        f5 -= 1
    elif(i == 7):
        f7 -= 1
        
if (f5 == 0 and f7 == 0):
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3060
def XOR(A, B):
    BA = int(A)
    BB = int(B)
    result = BA + BB
    result = str(result)
    result = result.replace('2', '0')
    result = int(result, 2)
    return result


L1 = input()
L2 = input()
L1 = L1.split()
L2 = L2.split()
for i, val in enumerate(L1):
    L1[i] = int(val)
K = L1[1]
K = bin(K)
K = K[2:]
lenK = len(K)
L3 = []
for i, val in enumerate(L2):
    L2[i] = int(val)
    L2[i] = bin(L2[i])
    lenL2i = len(L2[i])-2
    L2[i] = L2[i][2:]
    if lenL2i < lenK:
        dif = lenK - lenL2i
        for a in range(dif):
            L2[i] = '0' + L2[i]
        L3.append(L2[i])
    elif lenL2i == lenK:
        L3.append(L2[i])
    else:
        dif = lenL2i - lenK
        L3.append(L2[i][dif:])
final = ''
judgeFlag = 0
i = 0
finalJudge = 0
# print('K'+K)
if K == '0':
    final = '0'
else:
    while i < lenK:
        # print('roop'+str(i))
        # print(final)
        # print('judgeFlag' + str(judgeFlag))
        # print('finalJudge' + str(finalJudge))
        if (judgeFlag == 1) & (finalJudge == 0):
            if K[i] == '0':
                final += '0'
                i += 1
            else:
                # print(i)
                count_0 = 0
                count_1 = 0
                for each in L3:
                    if each[i] == '0':
                        count_1 += 1
                    else:
                        count_0 += 1
                if count_1 >= count_0:
                    final += '1'
                    judgeFlag = 1
                else:
                    final += '0'
                    finalJudge = 1
                i += 1
        else:
            # print(i)
            count_0 = 0
            count_1 = 0
            for each in L3:
                if each[i] == '0':
                    count_1 += 1
                else:
                    count_0 += 1
            if count_1 >= count_0:
                final += '1'
                judgeFlag = 1
            else:
                final += '0'
                finalJudge = 1
            i += 1
sumInt = 0
for each in L2:
    sumInt += XOR(final, each)
# print(final)
print(sumInt)

Measured memory_bytes: 21436
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;


struct Node {
    int v;
    Node* l;
    Node* r;
};

Node* root = NULL;

bool find(int v) {
    Node* x = root;
    while (x && x->v != v) {
        if (v < x->v) {
            x = x -> l;
        } else if (v > x-> v) {
            x = x -> r;
        } 
    }
    if (x && x->v == v) return true;
    return false;
}

void insert(int v) {
    if (!root) {
        root = new Node;
        root -> v = v;
        root -> l = NULL;
        root -> r = NULL;
        return;
    }

    Node* par = NULL;
    Node* x = root;
    while (x) {
        par = x;
        if (v < x -> v) {
            x = x -> l;
        } else {
            x = x -> r;
        }
    }
    if (v < par->v) {
        par -> l = new Node;
        Node* p = par -> l;
        p -> v = v;
        p -> l = NULL;
        p -> r = NULL;
    } else {
        par -> r = new Node;
        Node* p = par -> r;
        p -> v = v;
        p -> l = NULL;
        p -> r = NULL;
    }
}

void preOrder(Node* root) {
    if (root == NULL) return ;
    printf(" %d", root -> v);
    preOrder(root -> l);
    preOrder(root -> r);
}

void inOrder(Node* root) {
    if (root == NULL) return ;
    inOrder(root -> l);
    printf(" %d", root -> v);
    inOrder(root -> r);
}


int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n;
    int num;
    char s[10];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        if (s[0] == 'i') {
            scanf("%d", &num);
            insert(num);
        } else if (s[0] == 'p') {
            inOrder(root);
            printf("\n");
            preOrder(root);
            printf("\n");
        } else if (s[0] == 'f') {
            scanf("%d", &num);
            if (find(num)) printf("yes\n");
            else printf("no\n");
        }
    }
    return 0;
}

Measured memory_bytes: 15596
#include <stdio.h> 
int main(){
  int n;
  while(scanf("%d",&n)!=EOF){
    int a,b,c,d,k=0;
    for(a=0;a<=9;a++){
      for(b=0;b<=9;b++){
    for(c=0;c<=9;c++){
      for(d=0;d<=9;d++){
        if(a+b+c+d==n)k++;
      }
    }
      }
    }
    printf("%d\n",k);
  }
  return 0;
}


Measured memory_bytes: 2048
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	int P;
	List<int> ps;
	void Solve()
	{
		var N = F;
		if (N < 10) { WriteLine(0); return; }
		ps = GetPrimes(N); P = ps.Count;
		var fact = new Dictionary<int, int>();
		for (var n = 2; n <= N; n++) fact = Multiply(fact, Factorize(n, ps));
		var s = 0;
		foreach (var x in Calc1(74)) if (IsMultiple(fact, x)) s++;
		foreach (var x in Calc2(24, 2)) if (IsMultiple(fact, x)) s++;
		foreach (var x in Calc2(14, 4)) if (IsMultiple(fact, x)) s++;
		foreach (var x in Calc3(4, 2)) if (IsMultiple(fact, x)) s++;
		WriteLine(s);
	}
	IEnumerable<Dictionary<int, int>> Calc1(int e)
	{
		foreach (var p in ps) yield return new Dictionary<int, int> { [p] = e };
	}
	IEnumerable<Dictionary<int, int>> Calc2(int e, int f)
	{
		foreach (var p in ps) foreach (var q in ps) if (p != q) yield return new Dictionary<int, int> { [p] = e, [q] = f };
	}
	IEnumerable<Dictionary<int, int>> Calc3(int e, int f)
	{
		foreach (var p in ps) foreach (var q in ps) if (p < q) foreach (var r in ps) if (r != p && r != q) yield return new Dictionary<int, int> { [p] = e, [q] = e, [r] = f };
	}
	public static List<int> GetPrimes(int n)
	{
		var m = (n - 1) >> 1;
		var ps = new List<int>((int)(n / Log(n))) { 2 };
		var ng = new bool[m];
		ng[0] = false;
		for (var p = 0; p < m; p++)
			if (!ng[p])
			{
				var x = 2 * p + 3;
				ps.Add(x);
				for (var k = 3 * p + 3; k < m; k += x) ng[k] = true;
			}
		return ps;
	}
	public static Dictionary<int, int> Factorize(int n, List<int> primes)
	{
		var d = new Dictionary<int, int>();
		for (var j = 0; j < primes.Count; j++)
		{
			var i = primes[j];
			if (i * i > n) break;
			if (n % i == 0)
			{
				d.Add(i, 0);
				while (n % i == 0) { n /= i; d[i]++; }
			}
		}
		if (n > 1) d.Add(n, 1);
		return d;
	}
	public static Dictionary<int, int> Multiply(Dictionary<int, int> x, Dictionary<int, int> y)
	{
		var z = new Dictionary<int, int>();
		foreach (var t in x) z[t.Key] = t.Value + (y.ContainsKey(t.Key) ? y[t.Key] : 0);
		foreach (var t in y) if (!x.ContainsKey(t.Key)) z[t.Key] = t.Value;
		return z;
	}
	public static bool IsMultiple(Dictionary<int, int> x, Dictionary<int, int> y)
	{
		foreach (var t in y) if (!x.ContainsKey(t.Key) || x[t.Key] < t.Value) return false;
		return true;
	}
}


Measured memory_bytes: 13400
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x,a,b;
    cin >> x >> a >> b;
    if(a >= b)
    {
        cout << "delicious";
    }
    else if(b - a <= x)
    {
        cout << "safe";
    }
    else
    {
        cout << "dangerous";
    }
    
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<ll> a(n), prefix_sum(n + 1, 0);
    rep(i, n) {
        cin >> a[i];
        prefix_sum[i + 1] = prefix_sum[i] + a[i];
    }
    ll ans = 1e18;
    int left = 1, right = 3;
    for (int mid = 2; mid < n; mid++) {
        while(left + 1 < mid && abs(prefix_sum[mid] - prefix_sum[left] - prefix_sum[left]) > abs(prefix_sum[mid] - prefix_sum[left+1] - prefix_sum[left+1])){
            left++;
        }
        while(right + 1 <= n && abs(prefix_sum[n] - prefix_sum[right] - (prefix_sum[right] - prefix_sum[mid])) > abs(prefix_sum[n] - prefix_sum[right+1] - (prefix_sum[right+1] - prefix_sum[mid]))){
            right++;
        }
        ll b = prefix_sum[left];
        ll c = prefix_sum[mid] - prefix_sum[left];
        ll d = prefix_sum[right] - prefix_sum[mid];
        ll e = prefix_sum[n] - prefix_sum[right];
        ans = min(ans, max({b, c, d, e}) - min({b, c, d, e}));
    }
    cout << ans << endl;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define REP(i, a, b) for(long long i=a; i<=b; ++i)
#define REPN(i, a, b) for(long long i=a; i<=b; --i)
#define rep(i, a, b) for(long long i=a; i<b; ++i)
#define rep0(i,b) for(long long i=0; i<b; ++i)
#define REP0(i,b) for(long long i=0; i<=b; ++i)
#include<cmath>
#include <iomanip>
using namespace std;


typedef long long ll;



int main()
{
    int n;
    cin>>n;
    ll arr[n];
    rep0(i, n)
    {
        cin>>arr[i];
    }

    ll dp[n][n];

    memset(dp, 0, sizeof(dp));
    rep0(i, n)
    {
        dp[i][i] = arr[i];

    }


    for(int i=n-2; i>=0; --i)
    {

        for(int j=i+1; j<n; ++j)
        {

            dp[i][j] = max(arr[i] - dp[i+1][j], arr[j] - dp[i][j-1]);
        }

    }




    cout<<dp[0][n-1]<<endl;



    return 0;

}


Measured memory_bytes: 73912
#include<iostream>
#include<cstdio>
using namespace std;
long long a[100005];
int main()
{
	ios::sync_with_stdio(false);
	int n;
	scanf("%d",&n);
	long long sum(0);
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		a[x]+=x;
		sum+=x;
	}
	int q;
	scanf("%d",&q);
	int b,c;
	for(int i=0;i<q;i++){
		scanf("%d%d",&b,&c);
		long long tmp=a[b]/b*c;
		sum+=tmp-a[b];
		a[c]+=tmp;
		a[b]=0;
		printf("%lld\n",sum);
	} 
	
	return 0;
}

Measured memory_bytes: 4644
#include<iostream>
#include<cmath>
 
using namespace std;
 
int main() {
 
    long long int x, y, i = 1;
    int flag = 0;
    cin >> x >> y;
 
    while(i <= x || i <= y){
 
        if (abs(x - i) == abs(y - i)) {
            flag = 1;
            break;
        }
 
        i++;
    }
 
    if(!flag)
        cout << "IMPOSSIBLE" << endl;
    else
        cout << i << endl;
 
    return 0;
}

Measured memory_bytes: 256
INF = float('inf')

N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

def knapsack01(items, capW, INF):
    sumV = sum([v for w, v in items])
    dp = [0] + [INF]*sumV
    accV = 0
    for wi, vi in sorted(items, key=lambda x: x[1]):
        accV += vi
        for v in reversed(range(vi, min(sumV, accV)+1)):
            w0 = dp[v-vi] + wi
            if w0 < dp[v]:
                dp[v] = w0
    for v in reversed(range(sumV+1)):
        if dp[v] <= capW:
            return v

print(knapsack01(items, capW, INF))


Measured memory_bytes: 5740
import java.util.*;

class Main{

  public static void main(String args[]){

    Scanner s=new Scanner(System.in);
    String N=s.next();
    int box=0;
    int max=N.length();
    for(int i=0;i<max;i++){
      box+=N.charAt(i)-48;
    }
    System.out.println(box%9==0?"Yes":"No");
    
  }  
}

Measured memory_bytes: 40168
#include <cstdio>
#include <set>

using namespace std;
const int N=100005;
int fa[N],stx[N],sty[N],n,top=0;
set<int> s[N];

int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

void insert(int x,int y){
	if (s[x].find(y)!=s[x].end()){
		stx[++top]=x;sty[top]=y;
		s[x].erase(y);
		s[y].erase(x);
		return;
	}
	s[x].insert(y);
	s[y].insert(x);
}

void erase(int x,int y){
	x=find(x);y=find(y);
	if (x==y) return;
	if (s[x].size()<s[y].size()) swap(x,y);
	fa[y]=x;
	for (set<int>::iterator it=s[y].begin();it!=s[y].end();it++){
		int z=find(*it);s[z].erase(y);
		if (z!=x && z!=y) insert(x,z);
	}
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n*2-2;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		insert(x,y);
	}
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1;i<=top;i++) erase(stx[i],sty[i]);
	if (top==n-1) printf("YES\n");
		else printf("NO\n");
}

Measured memory_bytes: 26112
from itertools import groupby

N,K,Q=map(int,input().split())
#S=list(map(int,input().split()))


A=[0]*Q
for i in range(Q):
    A[i] = int(input())

ans=[K-Q]*N

A.sort()

for key,value in groupby(A):
    ans[key-1] = K-Q+ len(list(value))

for n in ans:
    if n > 0:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 53336
fn gcd(a:i64, b:i64) -> i64 {
    if a > b {
        gcd(b, a);
    }
    return if a == 0 { b } else { gcd(b % a, a) };
}

fn lcm(a:i64, b:i64) -> i64 {
    a * b / gcd(a,b)
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let input_vec = read_vec::<i64>();
    let a = input_vec[0];
    let b = input_vec[1];
    let c = input_vec[2];
    let d = input_vec[3];
    //println!("A = {}", a);
    //println!("B = {}", b);
    //println!("C = {}", c);
    //println!("D = {}", d);
    let my_lcm = lcm(c, d);
    let until_a = (a - 1) - ((a - 1) / c) - ((a - 1) / d) + ((a - 1) / my_lcm);
    let until_b = b - (b / c) - (b / d) + (b / my_lcm);
    //println!("until a {}", until_a);
    //println!("until b {}", until_b);
    //println!("gcd {}", my_gcd);
    //println!("lcm {}", my_lcm);
    //println!("anwer {}", until_b - until_a);
    println!("{}", until_b - until_a);
}

// 10 40 6 8
// 23
//      1   2   3   4    5  6s  7   8o  9
// 10  11  12s 13  14   15 16o 17  18s 19
// 20  21  22  23  24so 25 26  27  28  29
// 30s 31  32o 33  34   35 36s 37  38  39
// 40o


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
vector <int> des[5010];
int a[5010];
int dfs(int s,int pre)
{
	for (int k=0;k<des[s].size();k++) if (des[s][k]!=pre) if (a[des[s][k]]<a[s]) if (!dfs(des[s][k],s)) return 1;
	return 0;
}
int main()
{
	int n;scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		des[u].push_back(v);des[v].push_back(u);
	}
	for (int i=1;i<=n;i++) if (dfs(i,0)) printf("%d ",i);
}

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

int main(){
  int n;
  string s;
  int cnt=0;

  cin>>n;
  for(int i=0;i<n;i++){
    cin>>s;
    if(s=="A") cnt++;
    else cnt--;
    if(cnt<0){
      cout<<"NO"<<endl; return 0;
    }
  }
  if(cnt==0) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


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

int main (){
    int E,Y;
    cin >> E >> Y;

    if(E==0){
        if(Y>=1868&&Y<=1911){
            cout << "M" << Y-1867 << endl;
        }else if(Y>=1912&&Y<=1925){
            cout << "T" << Y-1911 << endl;
        }else if(Y>=1926&&Y<=1988){
            cout << "S" << Y-1925 << endl;
        }else{
            cout << "H" << Y-1988 << endl;
        }
    }else if(E==1){
        cout << 1867+Y << endl;
    }else if(E==2){
        cout << 1911+Y << endl;
    }else if(E==3){
        cout << 1925+Y << endl;
    }else{
        cout << 1988+Y << endl;
    }

    return 0;
}


Measured memory_bytes: 3120
#include<bits/stdc++.h>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=3e5+7;
const int INF=1e9;
char s[maxn];
int n;
int num1[maxn];
int num2[maxn];
int main()
{ 
   std::ios::sync_with_stdio(false);
   cin>>n;
   cin>>s+1;
   for(int i=1;i<=n;i++)
   {
      if(s[i]=='E')
        {
          num1[i]=num1[i-1]+1;
          num2[i]=num2[i-1];
        }
      else 
        {
          num2[i]=num2[i-1]+1;
          num1[i]=num1[i-1];
        }
   }
  int ans=1e9;
   for(int i=1;i<=n;i++)
   {
      if(s[i]=='E')
      {
        ans=min(ans,num1[n]-num1[i]+num2[i-1]);
      }
      else
      {
        ans=min(ans,num1[n]-num1[i]+num2[i-1]);
      }

   }
  cout<<ans;
 }

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

int N, M;
vector<pair<int, int>> AB;

int
main()
{
  cin >> N >> M;
  for (int i = 0; i < N; i++) {		//shop=N, max=M hon
    int a, b; cin >> a >> b;		//yen, hon
    AB.emplace_back(make_pair(a, b));
  }

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

  unsigned long long price = 0;
  for (int i = 0; i < N && 0 < M; i++) {
    if (AB.at(i).second > M) AB.at(i).second = M;
    price += (unsigned long long)AB.at(i).first * AB.at(i).second;
    M -= AB.at(i).second;
  }

  cout << price << endl;
}
/*
2 5
4 9
2 4
 */


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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
	string s;
	cin >> s;
	int n = s.size();
	if (s[0] == s[n - 1]) {
		if (n % 2) {
			cout << "Second" << endl;
		}
		else {
			cout << "First" << endl;
		}
	}
	else {
		if (n % 2) {
			cout << "First" << endl;
		}
		else {
			cout << "Second" << endl;
		}
	}
}

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

using namespace std;
#define intMax 2147483647
#define rep(i, a, b) for (long long i = a; i < b; i++)
#define repp(i, a, b) for (long long i = a; i >= b; i--)
#define be(a) (a.begin(), a.end())
#define rbe(p) (p.rbegin(), p.rend())
#define pb push_back

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n, m;
    cin >> n >> m;
    vector<pair<long long, long long>> A(n + 1);
    rep(i, 0, n)
    {
        cin >> A[i].first >> A[i].second;
    }
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 10, 0));
    long long maxi = 0;
    for (long long i = 1; i <= n; i++)
    {
        for (long long w = 1; w <= m; w++)
        {
            if (A[i - 1].first <= w)
            {
                dp[i][w] = max(A[i - 1].second + dp[i - 1][w - A[i - 1].first], dp[i - 1][w]);
            }
            else
            {
                dp[i][w] = dp[i - 1][w];
            }
            maxi = max(maxi, dp[i][w]);
        }
    }
    // rep(i, 0, m + 1)
    // {
    //     cout << dp[i] << " ";
    // }
    // cout << endl;
    cout << dp[n][m];
}

Measured memory_bytes: 80256
#include <iostream>
#include<algorithm>
#include <vector>
#include<string>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define max(x,y) (((x)>(y)) ? x:y)
#define min(x,y) (((x)<(y)) ? x:y)
#define FOR(a,b,c) for(b=(c);b<(a);b++)
#define ender {return 0;}
#define tosasuretu(a) (a*(a+1)/2)
inline ll kaizyo(ll);
ll gcd(ll, ll);
ll combination(ll, ll);
int main() {
	int N, M, X, Y;
	vector<int> x, y;
	cin >> N >> M >> X >> Y;
	int in;
	for (int i = 0; i < N; i++) {
		cin >> in;
		x.push_back(in);
	}
	for (int i = 0; i < M; i++) {
		cin >> in;
		y.push_back(in);
	}
	x.push_back(X);
	y.push_back(Y);
	sort(x.rbegin(), x.rend());
	sort(y.begin(), y.end());
	if (x[0]<y[0]) {
		cout << "No War";
	}
	else {
		cout << "War";
	}
	return 0;
}


inline ll kaizyo(ll x) {
	long ans = 1;
	for (int z = 0; z < x; z++) {
		ans *= (x - z);
	}
	return ans;
}
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a%b);
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>

using namespace std;

int main(void) {
    long long i, N, X;
    cin >> N;
    X = 0;
    if (N>0 && N-1LL != 1LL) X += N-1LL;
    for (i=2LL;i*i<=N;i++) {
        if (N%i == 0 && N/i != i && N/i != i+1) X += N/i-1LL;
    }
    cout << X << endl;

    return 0;
}

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

int main() {
	string s;
	cin >> s;
	if (s[2] == s[3] && s[4] == s[5]) cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

#define ll long long int
#define pii pair<int,int>
#define PII pair<ll,ll>

const int sz=1e3+100;
int n,m;
bool vis[sz][sz];
bool mark[sz][sz];
int tk[sz][sz];
queue<pii> q;
int dx[]={+1,-1,0,0};
int dy[]={0,0,+1,-1};

int dirx[]={-2,-1,0,+1,+2};
int diry[]={-2,-1,0,+1,+2};
string str[sz];

pii start,End;

bool check(int x,int y)
{
    if(x>=0 && y>=0 && x<n && y<m && vis[x][y]==false && str[x][y]=='.') return true;
    else return false;
}

void DFS(int x,int y,int deep)
{
    //cout<<x<<" "<<y<<endl;
    tk[x][y]=deep;
    vis[x][y]=true;
    q.push({x,y});
    for(int i=0;i<4;i++){
        int x1=x+dx[i];
        int y1=y+dy[i];
        if(check(x1,y1)){
           DFS(x1,y1,deep);
        }
    }
}


ll fun()
{
    DFS(start.first,start.second,0);
    q.push(start);

    while(!q.empty()){

        if(vis[End.first][End.second]==true) return tk[End.first][End.second];
        pii temp=q.front();
        q.pop();
        int x=temp.first, y=temp.second;
        if(mark[x][y]) continue;

        mark[x][y]=true;

        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                int x1=x+dirx[i];
                int y1=y+diry[j];
                if(check(x1,y1)) DFS(x1,y1,tk[x][y]+1);
            }
        }
    }

    if(vis[End.first][End.second]==true) return tk[End.first][End.second];
    return -1;
}

int main()
{
    cin>>n>>m;
    cin>>start.first>>start.second;
    cin>>End.first>>End.second;

    --start.first, --start.second;
    --End.first,  --End.second;

    memset(vis,false,sizeof vis);

    for(int i=0;i<n;i++) cin>>str[i];
    int ans=fun();
    cout<<ans<<'\n';
}




Measured memory_bytes: 12012
#include <iostream>

using namespace std;

int n, cnta, cntw, cntt, cntr;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        if (s == "AC") cnta++;
        if (s == "WA") cntw++;
        if (s == "TLE") cntt++;
        if (s == "RE") cntr++;
    }
    cout << "AC x " << cnta << endl;
    cout << "WA x " << cntw << endl;
    cout << "TLE x " << cntt << endl;
    cout << "RE x " << cntr << endl;
    return 0;
}

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

using ll = long long;

#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 ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

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

  int n, m; std::cin >> n >> m;
  ll sum = 0;
  vi a(n);
  rep(i, n) {
    std::cin >> a[i];
    sum += a[i];
  }
  int choice = 0;
  rep(i, n) {
    choice += (a[i] >= (sum+(4*m-1))/(4*m));
  }
  std::cout << (choice >= m ? "Yes" : "No") << "\n";
}


Measured memory_bytes: 256