akhauriyash/Code-Regression huggingface dataset:
// 
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define e_b emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ipair;
typedef pair<ll,ll> lpair;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v) //vectorの中身を見る
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
void map_p(map<int,int>& d){cout<<"map: ";for(auto a : d){cout<<"{"<<a.first<<":"<<a.second<<"}";}cout<<endl;} //mapの中身を見る
void set_p(set<int>& d){cout<<"set: ";for(int a : d){cout<<a<<" ";}cout<<endl;} //setの中身を見る


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

    string s,t;
    cin>>s>>t;
    int ans=0;
    int l=s.size();
    rep(i,l){
        if(s[i]!=t[i]) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3888
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<long long,int> P;
static const int INF=1<<24;

int n;

int main(){
	while(cin>>n,n){
		vector<int> sum;
		rep(i,n){
			sum.PB(0);
			rep(j,5){
				int t;
				cin>>t;
				sum[i]+=t;
			}
		}
		sort(ALL(sum));
		cout<<sum[sum.size()-1]<<" "<<sum[0]<<endl;
	}
	return 0;
}

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

int main() {
    char b; cin >> b;
    vector<vector<char>> a = {{'A','T'},{'C','G'},{'G','C'},{'T','A'}};
    rep(i,4){
        if(a[i][0] == b) cout << a[i][1] << endl;
    }
}


Measured memory_bytes: 256
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()

kyoutu = []

for i in range(1,31):
    kyoutu.append(i)

for _ in range(n):
    A = inintl()
    t = A[1:]
    kyoutu = set(kyoutu) & set(t)

print(len(kyoutu))

Measured memory_bytes: 62464
import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        String st;
        char a,b='a';
        Stack<Character> sta = new Stack<Character>();
        int i,j;
        boolean ch =true;
        while(true){
            st = s.nextLine();
            if(st.equals("."))break;
            for(i=0;i<st.length();i++){
                if(ch==false)break;
                a = st.charAt(i);
                if(a=='(')sta.push(a);
                if(a=='[')sta.push(a);
                if((a==')'||a==']')&&sta.empty())ch=false;
                if((a==')'||a==']')&&sta.size()>0)b = sta.pop();
                if(a==')'&&b!='(')ch=false;
                if(a==']'&&b!='[')ch=false;
            }
            if(sta.size()>0)ch = false;
            if(ch==true)System.out.println("yes");
            else System.out.println("no");
            ch=true;
            while(sta.size()>0)sta.pop();
        }
    }
}


Measured memory_bytes: 44788
import math

h, w = input().split()

h, w = int(h), int(w)

if (h == 1) or (w == 1):
  print(1)
else:
  print(math.ceil(max([h, w]) / 2) * math.ceil(min([h, w]) / 2) + math.floor(max([h, w]) / 2) * math.floor(min([h, w]) / 2))

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

int main(){
  int n, m;
  cin >> n >> m;
  int k=0;
  
  for(int i=0;i<n;i++){
    int x;
    cin >> x;
    k+=min(x,m-x);
  }
  
  cout << 2*k << endl;
  
}

Measured memory_bytes: 256
(let ((a (read))
      (b (read))
      (s (read-line)))
  (princ
   (if (and (= (length s) (+ a b 1))
            (char= (aref s a) #\-)
            (not (member #\- (concatenate 'list
                                          (subseq s 0 a)
                                          (subseq s (1+ a) (+ a b 1))))))
       "Yes"
       "No"))
  (terpri))

Measured memory_bytes: 13284
# https://juppy.hatenablog.com/entry/2018/11/08/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC_heapq_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3
n, m = map(int, input().split())
a = list(map(int, input().split()))
A = [-int(x) for x in a]

import heapq
heapq.heapify(A)

for i in range(m):
    y = heapq.heappop(A)
    heapq.heappush(A, -(-y//2))
    
print(-sum(A))

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

int main(){
  int X, N;
  std::cin >> X >> N;
  std::vector<int> p(N);
  std::map<int, int> list;
  for(int i = 0 ; i < N ; i++){
    std::cin >> p[i];
    list[p[i]] = 1;
  }
  if(N == 0){
    std::cout << X <<std::endl;
    return 0;
  }

  std::sort(p.begin(), p.end());
  
  std::vector<int> flist;
  for(int i = 0 ; i <= 101 ; i++){
    if(list[i] != 1){
      flist.push_back(i);
    }
  }
  auto it = std::upper_bound(flist.begin(), flist.end(), X);
  if( std::fabs(*it - X) >= std::fabs(*(it - 1) - X)){
    std::cout << *(it - 1) << std::endl;
  }else{
    std::cout << *it << std::endl;
  }
  return 0;
}



Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <sstream>
#include <map>
#include <cstring>
#include <vector>
#include <queue>
#include <iomanip>
#include <stack>
#include <unordered_set>

using namespace std;
typedef long long ll;

ll ans, mx, sum, mn = 1e14, cnt;



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

ll b[10000000],c[1000000];
int main(){
	ll n;
	cin>>n;
	ll a[n];
	for(ll i=0; i<n; i++){
		cin>>a[i];
	}
	ll first=a[0];
	b[0]=a[0];
	for(ll i=1; i<n; i++){
		first =gcd(first,a[i]);
		b[i]=first;
		//mx=max(mx,first);
	}
	ll sec=a[n-1];
	c[n-1]=a[n-1];
	for(ll i=n-2; i>=0; i--){
		sec=gcd(sec,a[i]);
		c[i]=sec;
		//mx=max(mx,sec);
	}
	if(n==2){
		ll j= max(a[0],a[1]);
		ll f=gcd(a[0],a[1]);
		cout<<max(f,j);
		return 0;
	}
	
	
	for(ll i=1; i<n; i++){
		
		ll j=gcd(b[i-1],c[i+1]);
		mx=max(mx,j);
	}
	ll p= max(mx,c[1]);
	ll v=max(p,b[n-2]);
	cout<<v;
}



Measured memory_bytes: 5848
#include<stdio.h>

int main(){
	int r,g,b,n;
	scanf("%d%d%d%d",&r,&g,&b,&n);
	int ans=0,i,j;
	for(i=0;i*r<=n;i++){
		for(j=0;j*g+i*r<=n;j++){
			if((n-r*i-j*g)%b==0)ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
char s[400];
int memo[310][310][310], n;
bool done[310][310][310];
int dp(int i, int j, int k)
{
	if (i > j) return 0;
	if (i == n) return 0;
	if (j == -1) return 0;
	if (done[i][j][k]) return memo[i][j][k];
	done[i][j][k] = true;
	int ans = dp(i+1, j, k);
	ans = max(ans, dp(i, j-1, k));
	if (s[i] == s[j]) ans = max(ans, dp(i+1, j-1, k)+1+(i != j));
	if (k)
	{
		ans = max(ans, dp(i+1, j-1, k-1)+1 + (i != j));
	}
	//printf("%d %d %d - %d\n", i, j, k, ans);
	return memo[i][j][k] = ans;
}
int main()
{
	scanf(" %s", s);
	n = strlen(s);
	int k;
	scanf("%d", &k);
	int ans = dp(0, n-1, k);
	printf("%d\n", ans);
}


Measured memory_bytes: 143616
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;
using ll = long long;

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<ll> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	vector<ll> b(n), c(n);
	b[0] = a[0];
	for(int i = 1; i < n; ++i){ b[i] = min(b[i - 1], a[i]); }
	c[n - 1] = a[n - 1];
	for(int i = n - 2; i >= 0; --i){ c[i] = max(c[i + 1], a[i]); }
	vector<ll> d(n);
	for(int i = 0; i < n; ++i){ d[i] = c[i] - b[i]; }
	const auto d_max = *max_element(d.begin(), d.end());
	unordered_map<ll, int> first_map, last_map;
	for(int i = n - 1; i >= 0; --i){ first_map[a[i]] = i; }
	for(int i = 0; i < n; ++i){ last_map[a[i]] = i; }
	unordered_map<ll, int> high, low;
	for(int i = 0; i < n; ++i){
		const auto lit = last_map.find(a[i] + d_max);
		if(lit != last_map.end() && i < lit->second){ low[a[i]]++; }
		const auto fit = first_map.find(a[i] - d_max);
		if(fit != first_map.end() && fit->second < i){ high[a[i]]++; }
	}
	int answer = 0;
	for(const auto p : low){
		const auto it = high.find(p.first + d_max);
		if(it != high.end()){
			answer += min(p.second, it->second);
		}
	}
	cout << answer << endl;
	return 0;
}



Measured memory_bytes: 15780
// Last Change: 04/24/2019 01:00:20.
//////////////////////////////////////////////////////////////////////////////
// Qのtopまわりがわけわからんくなっている
// topの戻り値が参照なのは分かったけど...
//////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

namespace NS {
void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}
} // namespace NS

class Data {
public:
  ll a, b, c;
  ll val;
  Data(ll p, ll q, ll r, ll s) : a(p), b(q), c(r), val(s) {
  }
  bool operator<(const Data &another) const {
    return this->val < another.val;
  }
};

int main() {
  ll X, Y, Z, K;
  cin >> X >> Y >> Z >> K;

  vector<ll> A(X);
  vector<ll> B(Y);
  vector<ll> C(Z);
  for (auto &&e : A) {
    cin >> e;
  }
  for (auto &&e : B) {
    cin >> e;
  }
  for (auto &&e : C) {
    cin >> e;
  }

  sort(A.begin(), A.end(), greater<ll>());
  sort(B.begin(), B.end(), greater<ll>());
  sort(C.begin(), C.end(), greater<ll>());

  priority_queue<Data> Q;
  vector<vector<vector<bool>>> memo(
      X, vector<vector<bool>>(Y, vector<bool>(Z, false)));

  // LLをつけないとコンストラクタがうまく呼ばれない
  //見えないバグなので要注意
  Q.push(Data(0LL, 0LL, 0LL, A[0] + B[0] + C[0]));
  ll cnt = 0;
  while (cnt < K) {
    ++cnt;

    /*
     * 参照で受け取ると、qに値を追加したときに参照先が行方不明になってしまう。
    const Data &tmp = Q.top();
    cout << tmp.val << endl;
    cout << Q.top().a << ' ' << Q.top().b << ' ' << Q.top().c << endl;
    if (tmp.a + 1 < X and memo[tmp.a + 1][tmp.b][tmp.c] == false) {
      memo[tmp.a + 1][tmp.b][tmp.c] = true;
      Q.push(Data(tmp.a + 1, tmp.b, tmp.c, A[tmp.a + 1] + B[tmp.b] + C[tmp.c]));
    }
    if (tmp.b + 1 < Y and memo[tmp.a][tmp.b + 1][tmp.c] == false) {
      memo[tmp.a][tmp.b + 1][tmp.c] = true;
      Q.push(Data(tmp.a, tmp.b + 1, tmp.c, A[tmp.a] + B[tmp.b + 1] + C[tmp.c]));
    }
    if (tmp.c + 1 < Z and memo[tmp.a][tmp.b][tmp.c + 1] == false) {
      cout << tmp.val << endl;
      memo[tmp.a][tmp.b][tmp.c + 1] = true;
      Q.push(Data(tmp.a, tmp.b, tmp.c + 1, A[tmp.a] + B[tmp.b] + C[tmp.c + 1]));
    }
    Q.pop();
    */

    const Data tmp = Q.top();
    Q.pop();
    cout << tmp.val << endl;
    if (tmp.a + 1 < X and memo[tmp.a + 1][tmp.b][tmp.c] == false) {
      memo[tmp.a + 1][tmp.b][tmp.c] = true;
      Q.push(Data(tmp.a + 1, tmp.b, tmp.c, A[tmp.a + 1] + B[tmp.b] + C[tmp.c]));
    }
    if (tmp.b + 1 < Y and memo[tmp.a][tmp.b + 1][tmp.c] == false) {
      memo[tmp.a][tmp.b + 1][tmp.c] = true;
      Q.push(Data(tmp.a, tmp.b + 1, tmp.c, A[tmp.a] + B[tmp.b + 1] + C[tmp.c]));
    }
    if (tmp.c + 1 < Z and memo[tmp.a][tmp.b][tmp.c + 1] == false) {
      memo[tmp.a][tmp.b][tmp.c + 1] = true;
      Q.push(Data(tmp.a, tmp.b, tmp.c + 1, A[tmp.a] + B[tmp.b] + C[tmp.c + 1]));
    }
  }

  //NS::LoopUntilZeroInpput();
}


Measured memory_bytes: 164736
#include <stdio.h> 

int main(void)
{
	int m,n,c,i,j;
	
	scanf("%d %d",&n,&m);
	
	int a[n][m],b[m];
	
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
			scanf("%d",&a[i][j]);
	}
	
	for(i=0;i<m;i++)
		scanf("%d",&b[i]);
		
	for(i=0;i<n;i++)
	{
		c = 0;
		for(j=0;j<m;j++)
			c = c+ a[i][j]*b[j];
		
		printf("%d\n",c);
		
	}
	
	return 0;
}

Measured memory_bytes: 636
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>

using namespace std;

typedef long long int lli;

int gcd(int a, int b) {
	return b != 0 ? gcd(b, a%b) : a;
}
lli gcd(lli a, lli b) {
	return b != 0 ? gcd(b, a%b) : a;
}
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}
lli lcm(lli a, lli b) {
	return a * b / gcd(a, b);
}

#define N_MAX 50
#define MOD 1000000007

void solv()
{
	int N; scanf("%d", &N);
	char s[N_MAX][200]; int t[N_MAX];
	for (int i = 0; i < N; i++) {
		scanf("%s%d", s[i], t + i);
	}

	char X[200]; scanf("%s", X);
	bool sleep = false; int ret = 0;
	for (int i = 0; i < N; i++) {
		if (sleep) {
			ret += t[i];
		}
		if (0 == strcmp(s[i], X)) {
			sleep = true;
		}
	}

	printf("%d", ret);

	return;
}

int main()
{
	FILE *fin = NULL, *fout = NULL;
	//fin = freopen("input.txt", "r", stdin);
	//fout = freopen("output.txt", "w", stdout);

	solv();

	//finalize
	if (NULL != fin) fclose(fin);
	if (NULL != fout) fclose(fout);

	return 0;
}


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

ll binpow(ll a, ll b) {
    if (b == 0)
    {
        return 1;
    }
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
    {
        return res * a;
    }
    return res;
}

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

string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int k,a,b;
    cin>>k;
    cin>>a>>b;
    if (a%k==0||b%k==0)
        cout<<"OK";
    else if (a/k==b/k)
        cout<<"NG";
    else
        cout<<"OK";
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n, m, x, y;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	cin >> n >> m;
	ll box[n+1];
	bool red[n+1];
	rep(i, 1, n){box[i] = 1;}
	memset(red, 0, sizeof(red));
	red[1] = true;
	
	rep(j, 1, m){
		cin >> x >> y;
		if(red[x]){
			red[y] = true;
		}
		if(box[x] == 1){
			red[x] = false;
		}
		box[x]--;
		box[y]++;
	}
	
	ll ans = 0;
	rep(i, 1, n){
		if(red[i]){
			ans++;
		}	
	}
	print(ans)
	return 0;
}

Measured memory_bytes: 1152
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.math.*;
 
public class Main {
	static HashMap<String, Integer> map = new HashMap<String, Integer>();
	static int[] l,r;
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
			
		String[] str = br.readLine().split(" ");
		int a = Integer.parseInt(str[0]);
		int b = Integer.parseInt(str[1]);
		System.out.println((a+b)%24);
	}
}


Measured memory_bytes: 20948
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
loo = []

for i in range(n):
    a,b = na()
    loo.append([b,a])

loo = sorted(loo)

t = 0
for i in loo:
    t += i[1]
    if t > i[0]:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 73436
import copy
from collections import deque

h, w = map(int,input().split())

input_maze=[]
for i in range(h):
	input_maze.append(list(input()))

maze=[[-1 for j in range(w+2)] for i in range(h+2)]

#banpei
for i in range(h):
    for j in range(w):
        if input_maze[i][j]=='.':
            maze[i+1][j+1]=0
        else:
            maze[i+1][j+1]=-1

#print(maze)

max_route=0
direction=[[1,0],[-1,0],[0,1],[0,-1]]
for i in range(h):
    for j in range(w):
        copy_maze=copy.deepcopy(maze)
        start=[i+1,j+1]
        que=deque([])
        if maze[start[0]][start[1]]==0:
            copy_maze[start[0]][start[1]]=-1
            for d in direction:
                if copy_maze[start[0]+d[0]][start[1]+d[1]]==0:
                    que.append([start[0]+d[0],start[1]+d[1]])
                    copy_maze[start[0]+d[0]][start[1]+d[1]]=1
                    if max_route<1:
                    	max_route=1
            while len(que)>0:
                tmp=que.popleft()
                for d in direction:
                    if copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]==0:
                        que.append([tmp[0]+d[0],tmp[1]+d[1]])
                        copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]=copy_maze[tmp[0]][tmp[1]]+1
                        if max_route<copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]:
                            max_route=copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]

                
print(max_route)

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

//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

//#define int long long
#define ll long long

ll INF = (1LL << 60);
int mod = 998244353;
using P = pair<int, int>;



signed main() {
	int N; cin >> N;
	vector<ll>A(N);
	for (int i = 0; i < N; i++) {
		double a; cin >> a;
		A[i] = (ll)llround(a * 1e9);
	}
	map<P, int>cnt;
	for (int i = 0; i < N; i++) {
		int cnt2 = 0, cnt5 = 0;
		while (A[i] % 2 == 0) {
			cnt2++;
			A[i] /= 2;
		}
		while (A[i] % 5 == 0) {
			cnt5++;
			A[i] /= 5;
		}
		cnt[{cnt2, cnt5}]++;
	}
	ll ans = 0;
	for (auto p1 : cnt) {
		for (auto p2 : cnt) {
			if (p1.first.first + p2.first.first >= 18 && p1.first.second + p2.first.second >= 18) {
				if (p1 < p2) {
					ans += (ll)p1.second*p2.second;
				}
				else if(p1 == p2){
					ans += (ll)p1.second*(p1.second - 1) / 2;
				}
			}

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


Measured memory_bytes: 4904
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;
typedef long long LL;
const int maxn = 100005;

int ehead[maxn],ecnt;
char s[2][10]={"NO","YES"};
struct edge {
	int u,v,next;
}edg[maxn*2];
LL f[maxn];int n,deg[maxn],a[maxn];
void add(int u,int v) {
	edg[++ecnt]=(edge){u,v,ehead[u]};
	ehead[u]=ecnt;deg[u]++;
	edg[++ecnt]=(edge){v,u,ehead[v]};
	ehead[v]=ecnt;deg[v]++;
}
bool dp(int u,int fa) {
	bool res=true;
	if (deg[u]<=1) {f[u]=a[u];return 1;}
	LL sum=0,mx=0;
	for (int v,j=ehead[u];j;j=edg[j].next)
	if ((v=edg[j].v)!=fa) {
		res&=dp(v,u);sum+=f[v];mx=max(mx,f[v]);
	}
	LL t=sum-a[u];f[u]=sum-2*t;
	res&=(f[u]>=0&&t>=0&&sum-mx>=t);
	return res;
}
int main()
{
	#ifdef Amberframe
		freopen("agc010c.in","r",stdin);
		freopen("agc010c.out","w",stdout);
	#endif
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int u,v,i=1;i<n;i++)
		scanf("%d %d",&u,&v),add(u,v);
	if (n==1) printf("%s",s[a[1]==0]);
	if (n==2) printf("%s",s[a[2]==a[1]]);
	if (n>2) {
		int rt=0;
		for (int i=1;i<=n;i++)
			if (deg[i]>1) rt=i;
		printf("%s",s[dp(rt,0)&&f[rt]==0]);
	}
	return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];

    ll ans = 1000000000000000;
    rep(s, -1, 2)
    {
        if (s == 0) continue;

        ll prev_sum = a[0];
        ll cnt;
        if (prev_sum * s <= 0)
        {
            cnt = abs(prev_sum) + 1;
            prev_sum = s;
        }
        else 
            cnt = 0;

        rep(i, 1, n)
        {
            ll now_sum = prev_sum + a[i];
            if (now_sum * prev_sum >= 0)
            {
                cnt += abs(now_sum) + 1;
                now_sum = (0 < prev_sum)? -1: 1;
            }
            prev_sum = now_sum;
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

class cProcess
{
	vector<pair<string, int>> vfinish;
	int etime;

	void output();

public:
	cProcess(int qua,queue<pair<string, int>> p)
	{
		etime = 0;
		pair<string, int> tp;

		while (!p.empty())
		{

			tp = p.front();
			p.pop();
			if ((tp.second - qua) > 0)
			{
				etime += qua;
				tp.second -= qua;
				p.push(tp);
			}
			else
			{
				etime += tp.second;
				vfinish.push_back(pair <string, int>(tp.first, etime));
			}
		}
		output();
	}
};

void cProcess::output()
{
	for (int i = 0; i < vfinish.size(); ++i)
	{
		cout << vfinish[i].first << " " << vfinish[i].second << endl;
	}
}

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

	queue<pair<string, int>> qp;

	for (int i = 0; i < n; ++i)
	{
		string tn;
		int tt;
		cin >> tn >> tt;
		pair<string, int> tp(tn, tt);
		qp.push(tp);
	}

	cProcess cp(q,qp);

	return 0;
}

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

int main()
{
  int a, b, m;
  cin >> a >> b >> m;
  vector<int> reizo(a);
  vector<int> densi(b);
  int minrei = INT_MAX;
  rep(i, a)
  {
    cin >> reizo[i];
    minrei = min(minrei, reizo[i]);
  }
  int minden = INT_MAX;
  rep(j, b)
  {
    cin >> densi[j];
    minden = min(minden, densi[j]);
  }
  int ans = minrei + minden;
  rep(i, m)
  {
    int x, y, c;
    cin >> x >> y >> c;
    x--; y--;
    ans = min(ans, reizo[x] + densi[y] - c);
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string> 
#include <vector>
using namespace std;

int main(void) {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if ((a + b) > (c + d))	cout << "Left" << endl;
	if ((a + b) == (c + d)) cout << "Balanced" << endl;
	if ((a + b) < (c + d))	cout << "Right" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;

int main(){
  int n;
  int num=1,max=0;
  int tmpnum,tmp;
    cin>>n;
    while(n){
        cin>>tmpnum>>tmp;
        if(max==tmp){
            if(num>tmpnum){
                num=tmpnum;
                --n;
                continue;
            }
        }
        if(max<tmp){
            num=tmpnum;
            max=tmp;
        }
        --n;
    }
    cout<<num<<" "<<max<<endl;
  return 0;
}


Measured memory_bytes: 3100
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,k = li()
a = list(li())

acum = list(accumulate([0]+a))

cand = []
for i in range(n+1):
    for j in range(i+1,n+1):
        cand.append(acum[j] - acum[i])

ans = 0

for mask in range(40, -1, -1):
    satis = sum([bool(ci&(1<<mask)) for ci in cand])

    if satis >= k:
        ans += (1<<mask)
        nex = [ci for ci in cand if ci & (1<<mask)]
        cand = nex
        

print(ans)

Measured memory_bytes: 92084
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<list>
#include<queue>
#include<string.h>
#include<functional>
#include<stack>
#include<deque>
#include<string>
#include<limits.h>
#include<map>
#include<set>
#include<unordered_map>
#include<cmath>
#include<unordered_set>
#define int long long
using namespace std;

int ans;
int n;
vector<int>V;
int S = 1;
void DFS(int sum, int a) {//今a番目まで見て合計がsum
	if (a == V.size()) {
		if (sum == n) {
			ans += S;
		}
		return;
	}
	int b = 0;
	for (int c = a + 1; c < V.size(); c++) {
		b += V[c];
	}
	b *= 9;
	for (int i = -9; i <= 9; i++) {
		int d = sum + V[a] * i;
		if (abs(d - n) <= b) {
			int e = abs(i);
			e = 10 - e;
			if (i >= 0 && a == 0) {
				e--;
			}
			if (e == 0)return;
			S *= e;
			DFS(d, a + 1);
			S /= e;
		}
	}
}
signed main() {
	cin >> n;
	for (int i = 2; i <= 18; i++) {
		V.clear();
		int a = 1, b = pow(10, (i - 1));
		for (int j = 0; j < i / 2; j++) {
			V.push_back(b - a);
			a *= 10; b /= 10;
		}
		if (i & 1) {
			S *= 10;
		}
		DFS(0, 0);
		if (i & 1) {
			S /= 10;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_(i, n, m) for (int i = n; i < (int)(m); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define stoi stoll
//#define _GLIBCXX_DEBUG

signed main() {
  int N; cin >> N;
  vector<int> A(N), B(N);
  rep(i, N) cin >> A[i];
  rep(i, N) cin >> B[i];
  
  int s = 0;
  rep(i, N) s += (A[i]-B[i]);
  if(s < 0) {
    cout << -1 << endl;
    return 0;
  }
  
  vector<int> p(0), m(0);
  int ms = 0;
  rep(i, N) {
    int k = A[i]-B[i];
    if(k > 0) p.push_back(k);
    if(k < 0) {
      m.push_back(k);
      ms += -k;
    }
  }
  
  sort(all(p));
  reverse(all(p));
  
  int ans = m.size();
  rep(i, p.size()) {
    if(ms <= 0) {
      cout << ans << endl;
      return 0;
    }
    ms -= p[i];
    ans++;
  }
  
  cout << ans << endl;


    

}

Measured memory_bytes: 5844
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))


def main():
    min_money = float('inf')

    N,M,X = MAP()
    A = [LI() for _ in range(N)]

    from itertools import product

    for bit in product([0,1],repeat=N):
        ability = [0]*M
        money = 0

        for i in range(N):
            if bit[i] == 1:
                money += A[i][0]
                
                for j in range(M):
                    ability[j] += A[i][j+1]

        for aa in ability:
            if aa >= X:
                continue
            else:
                break
        else:
            min_money = min(min_money,money)
         
    if min_money == float('inf'):
        print(-1)
    else:
        print(min_money)
    
    return 




if __name__ == '__main__':
    main()


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

#define itf  ios_base::sync_with_stdio(false)
#define ct  cin.tie(NULL)

int Z[100002];

int step(int a[],int n,int i)
{
    if(i>=n)
    return 0;
    
    if(Z[i]!=-1)
    return Z[i];
    
    return (Z[i]=min(abs(a[i-1]-a[i])+step(a,n,i+1),abs(a[i-1]-a[i+1])+step(a,n,i+2)));
}

int main() {
    
    memset(Z,-1,sizeof(Z));
    int n;
    cin>>n;
    int a[n];
    
    for(int i=0;i<n;i++)
    cin>>a[i];
    
    cout<<step(a,n,1)<<" ";
	return 0;
}


Measured memory_bytes: 4864
N = int(input())
A = list(map(int,input().split()))
L = []
for i in range(N):
    L.append(i-A[i])
R = []
for j in range(N):
    R.append(j+A[j])
from collections import Counter
LL = Counter(L)
RR = Counter(R)
ans = 0
for k,v in RR.items():
    ans += v*LL[k]
print(ans)

Measured memory_bytes: 167344
using Kujikatsu003.Questions;
using Kujikatsu003.Extensions;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Kujikatsu003.Questions
{
    /// <summary>
    /// https://atcoder.jp/contests/abc062/tasks/abc062_a
    /// </summary>
    public class QuestionA : AtCoderQuestionBase
    {
        public override IEnumerable<object> Solve(TextReader inputStream)
        {
            var xy = inputStream.ReadIntArray();
            yield return GetGroup(xy[0]) == GetGroup(xy[1]) ? "Yes" : "No";
        }

        int GetGroup(int n)
        {
            switch (n)
            {
                case 2:
                    return 2;
                case 4:
                case 6:
                case 9:
                case 11:
                    return 1;
                default:
                    return 0;
            }
        }
    }
}


namespace Kujikatsu003
{
    class Program
    {
        static void Main(string[] args)
        {
            IAtCoderQuestion question = new QuestionA();    // 問題に合わせて書き換え
            var answers = question.Solve(Console.In);
            foreach (var answer in answers)
            {
                Console.WriteLine(answer);
            }
        }
    }
}

#region Base Classes

namespace Kujikatsu003.Questions
{

    public interface IAtCoderQuestion
    {
        IEnumerable<object> Solve(string input);
        IEnumerable<object> Solve(TextReader inputStream);
    }

    public abstract class AtCoderQuestionBase : IAtCoderQuestion
    {
        public IEnumerable<object> Solve(string input)
        {
            var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
            var reader = new StreamReader(stream, Encoding.Unicode);

            return Solve(reader);
        }

        public abstract IEnumerable<object> Solve(TextReader inputStream);
    }

}

#endregion

#region Extensions

namespace Kujikatsu003.Extensions
{
    internal static class TextReaderExtensions
    {
        internal static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
        internal static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
        internal static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
        internal static string ReadString(this TextReader reader) => reader.ReadLine();

        internal static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
        internal static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
        internal static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
        internal static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
    }
}

#endregion

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) (int)(a.size())

int main()
{	
	int n;
	cin >> n;
	cout << (n - 1) / 2;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
          
using namespace std;
          
typedef long long ll;
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define db long double

struct vert{
	int r, pred;
};

struct cnm{
	vert t[200007];

	cnm() { for (int i = 0; i < 200007; i++) t[i].r = 0, t[i].pred = i; }

	int get(int v){
		if (t[v].pred == v) return v;
		return t[v].pred = get(t[v].pred);
	}

	void merge(int a, int b){
		a = get(a);
		b = get(b);
		if (a != b){
			if (t[a].r < t[b].r) swap(a, b);
			t[b].pred = a;
			if (t[a].r == t[b].r) t[a].r++;
		}
	}
} cc;

int n;
int pred[200007];
int color[200007];
int tp[200007];
int x[200007], y[200007];

struct st{
	int v;

	st(){}
	st(int vv) { v = vv; }

	bool operator< (st nxt) const { 
		if (x[v] * (ll)y[nxt.v] == y[v] * (ll)x[nxt.v]) return v < nxt.v;
		return x[v] * (ll)y[nxt.v] > y[v] * (ll)x[nxt.v];
	}
}; 

set<st> se;

int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output1.txt", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) cin >> pred[i], pred[i]--;
    for (int i = 0; i < n; i++) cin >> color[i];

    for (int i = 0; i < n; i++){
    	st now;
    	x[i] = (color[i] == 0);
    	y[i] = (color[i] == 1);
    	now.v = i;
    	tp[i] = i;
    	se.insert(now);
    }

    ll ans = 0;

    int zz = 0;
    while(se.size() > 1){
    	auto now = se.begin();
    	if (tp[(*now).v] == 0) now++;
    	se.erase(now);
    	int v = (*now).v;
    	//cout << v + 1 << endl;
    	//if (v + 1 == 4) exit(0);
    	int pos = cc.get(pred[tp[v]]);

    	se.erase(st(pos));

    	ans += y[pos] * (ll)x[v];
    	int gg = tp[pos];
    	cc.merge(v, pos);
    	if (cc.get(v) == v){
    		x[v] += x[pos];
    		y[v] += y[pos];
    		tp[v] = tp[pos];
    		se.insert(st(v));
    	} else {
    		x[pos] += x[v];
    		y[pos] += y[v];
    		se.insert(st(pos));
    	}
    	//cout << endl;
    	zz++;
    	//if (zz == 10) exit(0);
    }
   //cout << endl;
    cout << ans;
}

Measured memory_bytes: 15744
#include<iostream>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long int ll;

string s;
int K;

int mem[110][110][3];

int calc(int n,int num,int isunder){
    if(mem[n][num][isunder]!=-1)return mem[n][num][isunder];
    if(n==s.size()){
        if(isunder==0)return 0;
        else {
            if(num==K)return 1;
            else return 0;
        }
    }
    int res=0;
    if(num==K)res++;
    for(int i=0;i<=9;++i){
        if(i==0&&n==0)continue;
        else{
            int _isunder;
            if(isunder==1)_isunder=1;
            else if(isunder==2&&s[n]-'0'==i)_isunder=2;
            else if(isunder==2&&s[n]-'0'>i)_isunder=1;
            else _isunder=0;
            if(i==0)res+=calc(n+1,num,_isunder);
            else res+=calc(n+1,num+1,_isunder);
        }
    }
    return mem[n][num][isunder]=res;
}

int main(){
    for(int i=0;i<110;++i)for(int j=0;j<110;++j)for(int k=0;k<3;++k)mem[i][j][k]=-1;
    cin>>s;
    cin>>K;
    cout<<calc(0,0,2)<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD =  1000000007;
vector<int> hen[100001];
bool used[100001];
int dfs(int a){
     int c=0,b,ans=0;
     used[a]=true;
    
     for(auto&& i : hen[a]){
       
          if(!used[i]){
               b=dfs(i);
               if(b==0)c++;
               ans+=b;
          }
     }
     return ans+max(0ll,c-1);
}
     signed main(){
     
    int n;
    cin>>n;
    int a,b;
    for(int i=0;i<n-1;i++){
         cin>>a>>b;
         hen[a].push_back(b);
         hen[b].push_back(a);
    }
     
    for(int i=0;i<n;i++){
         if(hen[i].size()>=3){
              cout<<dfs(i)<<endl;
              return 0;
         }
    }
    cout<<1<<endl;
      }

        


Measured memory_bytes: 8576
import sys
from collections import deque
input = sys.stdin.readline

N=int(input())
S=[input().strip() for i in range(N)]

E=[[] for i in range(N)]

for i in range(N):
    for j in range(N):
        if S[i][j]=="1":
            E[i].append(j)
            E[j].append(i)

USE=[-1]*N

Q=deque()
Q.append(0)
USE[0]=0


while Q:
    x=Q.pop()

    for to in E[x]:
        if USE[x]==USE[to]:
            print(-1)
            sys.exit()
            
        elif USE[to]==-1:
            USE[to]=1-USE[x]
            Q.append(to)

for i in range(N):
    for j in range(N):
        if S[i][j]=="1" and USE[i]==USE[j]:
            print(-1)
            sys.exit()

ANS=0
for i in range(N):
    Q=deque()
    Q.append(i)
    USE=[0]*N
    USE[i]=1
    H=[0]*N

    while Q:
        NQ=deque()
        while Q:
            
            x=Q.pop()

            for to in E[x]:
                if USE[to]==0:
                    H[to]=H[x]+1
                    USE[to]=1
                    NQ.append(to)

        Q=NQ

    ANS=max(ANS,max(H)+1)

print(ANS)

    


Measured memory_bytes: 43740
#include <iostream>
#define llint long long

using namespace std;

llint n;
llint l, r;
llint a[55];

int main(void)
{
	while(1){
		cin >> n >> l >> r;
		if(n == 0 && l == 0 && r == 0) break;
		
		llint ans = 0;
		for(int i = 1; i <= n; i++) cin >> a[i];
		for(int i = l; i <= r; i++){
			for(int j = 1; j <= n; j++){
				if(i%a[j] == 0){
					if(j%2) ans++;
					goto end;
				}
			}
			if(n%2==0) ans++;
			end:;
		}
		cout << ans << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3100
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

struct State{
  string grid[6][3];
  bool operator < (const State& s) const {
    REP(i, 6) REP(j, 3) if(grid[i][j] != s.grid[i][j]) return grid[i][j] < s.grid[i][j];
    return false;
  }
};
bool is_goal(State& s){
  return s.grid[0][2].find("*") != string::npos && s.grid[2][2].find("*") != string::npos;
}

void copy(string src[3], string dst[3]){
  REP(i, 3) dst[i] = src[i];
}

void rotate(string s[6][3], int a, int b, int c, int d){
  a--; b--; c--; d--;
  // a -> b -> c -> d
  string tmp[3];
  copy(s[d], tmp);
  copy(s[c], s[d]);
  copy(s[b], s[c]);
  copy(s[a], s[b]);
  copy(tmp, s[a]);
}

void revolve90(string s[3]){
  string tmp[3];
  copy(s, tmp);
  REP(y, 3) REP(x, 3){
    s[y][x] = tmp[2 - x][y];
  }
}

void revolve(string s[6][3], int k, int t){
  REP(_, t) revolve90(s[k - 1]);
}

State rotate(State s, int r){
  if(r >= 2){
    return rotate(rotate(rotate(s, r - 2), r - 2), r - 2);
  }
  State next;
  REP(i, 6) copy(s.grid[i], next.grid[i]);
  if(r == 0) rotate(next.grid, 1, 5, 3, 6);
  if(r == 1) rotate(next.grid, 2, 5, 4, 6);
  if(r == 0) {
    revolve(next.grid, 3, 2);
    revolve(next.grid, 6, 2);

    revolve(next.grid, 2, 1);
    revolve(next.grid, 4, 3);
  }
  if(r == 1){
    revolve(next.grid, 5, 1);
    revolve(next.grid, 4, 1);
    revolve(next.grid, 6, 1);
    revolve(next.grid, 2, 1);

    revolve(next.grid, 1, 3);
    revolve(next.grid, 3, 1);
  }
  return next;
}

void print(State s){
  REP(i, 6){
    printf("--- %d ---\n", i + 1);
    REP(j, 3) cout << s.grid[i][j] << endl;
  }
}

int main(){
  while(true){
    State start;
    REP(i, 6) REP(j, 3) cin >> start.grid[i][j];
    if(cin.eof()) break;
    map<State, int> dist;
    queue<State> que;
    dist[start] = 0;
    que.push(start);
    while(!que.empty()){
      State s = que.front(); que.pop();
      if(is_goal(s)){
        cout << dist[s] << endl;
        break;
      }
      REP(r, 4){
        State next = rotate(s, r);
        if(!dist.count(next)){
          dist[next] = dist[s] + 1;
          que.push(next);
        }
      }
    }
  }
  return 0;
}

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

namespace AtCoder035
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            int[] A = Console.ReadLine().Split().Select(x => Convert.ToInt32(x)).ToArray();
            IDictionary<int, int> mp = new Dictionary<int, int>();
            for (int i = 0; i < N; ++i)
            {
                if (!mp.ContainsKey(A[i]))
                    mp.Add(A[i], 0);
                ++mp[A[i]];
            }

            if(mp.Count == 1)
            {
                if (mp.ContainsKey(0))
                    Console.WriteLine("Yes");
                else
                    Console.WriteLine("No");
                return;
            }

            if(mp.Count > 3)
            {
                Console.WriteLine("No");
                return;
            }

            if(N == 3 && (A[0] ^ A[1] ^ A[2]) == 0)
            {
                Console.WriteLine("Yes");
                return;
            }


            if (mp.Count == 2)
            {
                if(!mp.ContainsKey(0))
                {
                    Console.WriteLine("No");
                    return;
                }
                int[] vl = mp.OrderBy(x => x.Key).Select(x => x.Value).ToArray();
                if(2 * vl[0] == vl[1])
                    Console.WriteLine("Yes");
                else
                    Console.WriteLine("No");
                return;
            }

            KeyValuePair<int, int>[] kvp = mp.OrderBy(x => x.Value).ToArray();
            if ((kvp[0].Key ^ kvp[1].Key ^ kvp[2].Key) == 0 && kvp[0].Value == kvp[1].Value && kvp[1].Value == kvp[2].Value)
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
       }
    }
}

Measured memory_bytes: 23392
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <list>

int n;
int arr[100010];

int main() {
    std::cin >> n;

    for(int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    int cost = 1;
    long long cnt = 0;
    for(int i = 0; i < n; ++i) {
        int a = (arr[i] - 1) / cost;

        cnt += a;

        cost = std::max(cost, a == 0 ? arr[i] + 1 : 2);
    }

    std::cout << cnt << std::endl;
}

Measured memory_bytes: 768
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def bfs(sx, sy):
  que = deque([[sy,sx]])
  D =  [(0,1), (1,0), (0,-1), (-1,0)]

  DD =  [(-2,-2), (-2,-1), (-2,0), (-2,1), (-2, 2), \
  (-1,-2), (-1,-1), (-1,1), (-1, 2), \
  (0, -2), (0, 2), \
  (1,-2), (1,-1), (1,1), (1, 2), \
  (2,-2), (2,-1), (2,0), (2,1), (2, 2) ]

  while que:
    y,x = que.popleft()
    flag = 0
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "#"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]
          que.appendleft([y+j,x+i])
        elif(dist>G[y][x]):
          G[y+j][x+i] = G[y][x]
          que.appendleft([y+j,x+i])
      else:
        flag = 1
      if(flag == 1):
          flag = 0
          for k,l in DD:
              if(x+k<0 or y+l<0 or x+k>W-1 or y+l>H-1):
                  continue
              dist = G[y+l][x+k]
              #print(G[y][x])
              if(G[y+l][x+k] != "#"):
                  if(type(G[y+l][x+k]) is str):
                      G[y+l][x+k] = G[y][x]+1
                      que.append([y+l,x+k])
                  elif(dist>G[y][x]+1):
                      G[y+l][x+k] = G[y][x]+1
                      que.append([y+l,x+k])

sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

H, W = map(int, input().split())
magicY, magicX = map(int, input().split())
goalY, goalX = map(int, input().split())
G = [list(input()) for i in range(H)]
G[magicY-1][magicX-1] = 0
ans = 0

#print(G[magicX-1][magicY-1])

bfs(magicX-1, magicY-1)

if(G[goalY-1][goalX-1]=="."):
    print(-1)
else:
    print(G[goalY-1][goalX-1])


Measured memory_bytes: 173688
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// input scanner
var sc = bufio.NewScanner(os.Stdin)

const (
	initialBufSize = 10e4
	maxBufSize     = 10e6
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextInt64() int64 {
	a, _ := strconv.ParseInt(next(), 10, 64)
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

// util
func max(l []int) (int, int) {
	idx := 0
	ans := l[idx]
	for i, n := range l {
		if n > ans {
			idx = i
			ans = n
		}
	}
	return idx, ans
}

func min(l []int) (int, int) {
	idx := 0
	ans := l[idx]
	for i, n := range l {
		if n < ans {
			idx = i
			ans = n
		}
	}
	return idx, ans
}

func mul(a int64, b int64) int64 {
	return (a * b) % mod
}

func power(x int64, y int64) int64 {
	if y == 0 {
		return 1
	} else if y%2 == 0 {
		ans := int64(power(x, y/2)) % mod
		ans = mul(ans, ans)
		return ans
	} else {
		ans := int64(power(x, y/2)) % mod
		ans = mul(mul(ans, ans), x)
		return ans
	}
}

var mod = int64(1000000007)

func comb(n int, k int) int64 {
	x := int64(1)
	y := int64(1)
	for i := 0; i < k; i++ {
		x = mul((int64(n - i)), x)
		y = mul(int64(i+1), y)
	}
	invy := power(y, mod-2)
	return mul(x, invy)
}

// main
func main() {
	buf := make([]byte, initialBufSize)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords)
	n := nextInt()
	a := nextInt()
	b := nextInt()

	ans := power(2, int64(n)) - 1
	ans %= mod
	if ans < 0 {
		ans += mod
	}
	ans = ans - comb(n, a)
	ans %= mod
	if ans < 0 {
		ans += mod
	}
	ans = ans - comb(n, b)
	ans %= mod
	if ans < 0 {
		ans += mod
	}
	fmt.Println(ans)
}


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

using namespace std;
using ll = long long;
using pint = pair<int, int>;

int main() {
	int H, W, K;
	cin >> H >> W >> K;

	vector<string> c(H);
	for (int i = 0; i < H; ++i) {
		cin >> c[i];
	}

	int ans = 0;
	for (int h = 0; h < (1 << H); ++h) {
		vector<string> tmp = c;
		for (int i = 0; i < H; ++i) {
			if (h & (1 << i)) {
				for (int k = 0; k < tmp[i].size(); ++k) {
					tmp[i][k] = 'x';
				}
			}
		}

		for (int w = 0; w < (1 << W); ++w) {
			vector<string> tmp2 = tmp;

			for (int j = 0; j < W; ++j) {
				if (w & (1 << j)) {
					for (int k = 0; k < tmp2.size(); ++k) {
						tmp2[k][j] = 'x';
					}
				}
			}

			int count = 0;
			for (int i = 0; i < tmp2.size(); ++i) {
				for (int j = 0; j < W; ++j) {
					if (tmp2[i][j] == '#') {
						count++;
					}
				}
			}

			if (count == K) {
				ans++;
			}
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(n);i++)
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
int dp[50][500][500],a[50],b[50],c[50],n,ma,mb,ans=INF;
signed main(){
	cin>>n>>ma>>mb;
	rep(i,n)cin>>a[i]>>b[i]>>c[i];
	rep(i,50)rep(j,500)rep(k,500)dp[i][j][k]=INF;
	dp[0][0][0]=0;
	for(int i=1;i<=n;i++){
	    rep(j,500){
	        rep(k,500){
	            if(j<a[i-1]||k<b[i-1])dp[i][j][k]=dp[i-1][j][k];
	            else dp[i][j][k]=min(dp[i-1][j][k],dp[i-1][j-a[i-1]][k-b[i-1]]+c[i-1]);
	        }
	    }
	}
	for(int i=1;ma*i<500&&mb*i<1000;i++)ans=min(ans,dp[n][ma*i][mb*i]);
	if(ans==INF)cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 97920