akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <set>
#include <string>
#include <vector>

#include <array>
#define MOD 1000000007
#define INT_MAX 2000000000

using namespace std;

int gcd(int a,int b){
	if (!a) return b;
	if (!b) return a;
	a -= b;
	return gcd(max(a,b), min(a,b));
}

int main()
{
	string t, b;

	cin >> t >> b;

	int dp[1001][1001] = {};

	if (b[0] == t[0])
		dp[0][0] = 1;

	for (int i = 1; t.length() > i; i++){
		for (int j = 1; b.length() > j; j++){
			if (t[i] == b[j])
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
			else
				dp[i][j] = dp[i - 1][j];

			dp[i][j] %= MOD;
		}
		dp[i][0] = dp[i - 1][0];
		if (t[i] == b[0])
			dp[i][0]++;
		dp[i][0] %= MOD;
	}


	cout << dp[t.length() - 1][b.length() - 1] << endl;


	return 0;
}

Measured memory_bytes: 7108
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int MOD = 1000000007;
main(){
    ll N,A,B;
    cin >> N >> A >> B;
    if(A > B || (N == 1 && A != B)){
        cout << 0 << endl;
        return 0;
    }
    cout << (N-2)*(B-A)+1 << endl;
}

Measured memory_bytes: 256
##入力
N, M = list(map(int,input().split()))
sc = [list(map(int,input().split())) for _ in range(M)]
##最小の値を先にいれておく(10...0)
numl = [0 for _ in range(N)]
if N >= 2:
  numl[0] = 1
flag = 0
s = [sc[i][0] for i in range(M)]
c = [sc[i][1] for i in range(M)]
##数字を桁ごとにリストに入れる
for i in range(M):
  numl[s[i]-1] = c[i]
##最初の桁が0で2桁以上ならだめ
if numl[0] == 0 and N >= 2:
  flag += 1
##同じ桁で違う数字を指定されたらだめ
for i in range(0, M-1):
  for j in range(i+1, M):
    if s[i] == s[j] and c[i] != c[j]:
      flag += 1

#結果
if flag != 0:
  print(-1)
else:
  Numl = [str(a) for a in numl]
  num=''.join(Numl)
  print(num)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer num = Integer.parseInt(br.readLine());
		String[] inNumArrays = br.readLine().split(" ");
		long sum = 0;
		ArrayList<Integer> numArrayList = new ArrayList<Integer>();
		for (int i = 0; i < num; i++) {
			numArrayList.add(Integer.parseInt(inNumArrays[i]));
			sum += Integer.parseInt(inNumArrays[i]);
		}
		Collections.sort(numArrayList);
		System.out.println(numArrayList.get(0) + " " + numArrayList.get(numArrayList.size()-1) + " " + sum);
	}
}

Measured memory_bytes: 30200
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main{

	String input;
	int p;

	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			input = in.nextLine();
			if(input.equals("#")) return ;
			System.out.println(solve());
		}
	}

	int solve(){
		p = 0;
		return expr().size();
	}

	Set<Integer> rec(ArrayList<Set<Integer>> nums, ArrayList<Character> ops, ArrayList< ArrayList<Set<Integer> > > memo, int from, int to){
		if(memo.get(from).get(to) != null){
			return memo.get(from).get(to);
		}
		if(from == to){
			memo.get(from).set(to, nums.get(from));
			return memo.get(from).get(to);
		}
		Set<Integer> ret = new HashSet<Integer>();
		for(int i=from; i<to; i++){
			Integer[] x = rec(nums, ops, memo, from, i).toArray(new Integer[0]),
					y = rec(nums, ops, memo, i+1, to).toArray(new Integer[0]);
			for(int j=0; j<x.length; j++){
				for(int k=0; k<y.length; k++){
					if(ops.get(i) == '+'){
						ret.add(x[j].intValue() + y[k].intValue());
					}
					else if(ops.get(i) == '-'){
						ret.add(x[j].intValue() - y[k].intValue());
					}
					else if(ops.get(i) == '*'){
						ret.add(x[j].intValue() * y[k].intValue());
					}
					else if(ops.get(i) == '/' && y[k].intValue() != 0){
						ret.add(x[j].intValue() / y[k].intValue());
					}
				}
			}
		}
		memo.get(from).set(to, ret);
		return ret;
	}

	Set<Integer> expr(){
		ArrayList<Set<Integer>> nums = new ArrayList<Set<Integer>>();
		ArrayList<Character> ops = new ArrayList<Character>();
		while(p < input.length()){
			if(input.charAt(p) == '('){
				p++;
				nums.add(expr());
				p++;
			}
			else{
				nums.add(num());
			}
			if(p < input.length() && (input.charAt(p)=='+' || input.charAt(p)=='-' || input.charAt(p)=='*' || input.charAt(p)=='/')){
				ops.add(input.charAt(p++));
			}
			else{
				break;
			}
		}
		ArrayList< ArrayList<Set<Integer> > > memo = new ArrayList< ArrayList<Set<Integer> > >();
		for(int i=0; i<nums.size(); i++){
			memo.add(new ArrayList<Set<Integer> >());
			for(int j=0; j<nums.size(); j++){
				memo.get(i).add(null);
			}
		}
		Set<Integer> ret = rec(nums, ops, memo, 0, nums.size()-1);
		return ret;
	}

	Set<Integer> num(){
		int ret = input.charAt(p++) - '0';
		while(p < input.length() && Character.isDigit(input.charAt(p))){
			ret = ret*10 + input.charAt(p++) - '0';
		}
		Set<Integer> s = new HashSet<Integer>();
		s.add(ret);
		return s;
	}

	public static void main(String[] args){
		new Main().run();
	}
}

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

struct StCoin
{
  StCoin() :
    m_nCoin(0), m_nNum(0)
  { }
  StCoin(int nCoin, int nNum) :
    m_nCoin(nCoin), m_nNum(nNum)
  { }

  int m_nCoin;
  int m_nNum;
};

void fnInput(vector<StCoin>& rvoCoin, int& rnTrgKin)
{
  int nNum500, nNum100, nNum50;
  cin >> nNum500 >> nNum100 >> nNum50;

  int i = 0;
  StCoin oCoin500(500, nNum500);
  rvoCoin[i++] = oCoin500;
  StCoin oCoin100(100, nNum100);
  rvoCoin[i++] = oCoin100;
  StCoin oCoin50(50, nNum50);
  rvoCoin[i] = oCoin50;

  cin >> rnTrgKin;
}

int fnRcsSch(int nPos, int nTrgKin, const vector<StCoin>& cnrvoCoin, int& rnSuccess)
{
  if (!nTrgKin)
  {
    rnSuccess++;
    return 1;
  }
  if (nTrgKin < 0)              return 1;
  if (nPos == cnrvoCoin.size()) return 0;

  for (int i = 0; i <= cnrvoCoin[nPos].m_nNum; i++)
    if (fnRcsSch(nPos + 1, nTrgKin - cnrvoCoin[nPos].m_nCoin * i, cnrvoCoin, rnSuccess))
      break;

  return 0;
}

void fnExhSch(int nTrgKin, const vector<StCoin>& cnrvoCoin)
{
  int nSuccess = 0;
  fnRcsSch(0, nTrgKin, cnrvoCoin, nSuccess);
  cout << nSuccess << endl;
}

int main()
{
  vector<StCoin> voCoin(3);
  int nTrgKin;

  fnInput(voCoin, nTrgKin);
  fnExhSch(nTrgKin, voCoin);

  return 0;
}
 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int count = 0;
  for(int i = 0; i < S.length(); i++){
  	if(S.at(i) == '1'){
    	count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
from enum import Enum
from queue import Queue

import numpy as np

import collections
import bisect
import sys
import math

from scipy.sparse.csgraph import floyd_warshall

BIG_NUM = 200000000000
MOD = 1000000007
EPS = 0.000000001

N = int(input())
ans='No'
for i in range(0,10):
    for j in range(i,10):
        if i*j == N:
            ans='Yes'
            break
print(ans)

Measured memory_bytes: 16748
n,k = map(int,input().split())
a = list(map(int,input().split()))

tt = [0] * n
tt[0] = 1
ans_l = [1]
i = 1

for j in range(k):
    i = a[i-1]
    if tt[i-1] == False:
        tt[i-1] = 1
        ans_l.append(i)
    else:
        break

d = ans_l.index(i)
k -= d
ans = k % (len(ans_l)-d)
print(ans_l[ans+d])


Measured memory_bytes: 102288
// 27DTG
// 04072020
#include<bits/stdc++.h>
using namespace std;
#define bolt ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef long double ld;
const ld pi=3.1415926535897932384626433;
const int mod = 1e9+7;
int main()
{
   bolt;
   ll n;
   cin>>n;
   map <string,ll> mp;
   while (n--)
   {
      string s;
      cin>>s;
      mp[s]++;
   }
   cout<<"AC x "<<mp["AC"]<<endl;
   cout<<"WA x "<<mp["WA"]<<endl;
   cout<<"TLE x "<<mp["TLE"]<<endl;
   cout<<"RE x "<<mp["RE"]<<endl;
}


Measured memory_bytes: 3660
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<list>
#include <cstring>
#include <functional>
//#include<unordered_map>
//#include<unordered_set>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF ((Int)1<<60)
#define EPS (1e-10)
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=1; i<=(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long Int;
typedef pair<Int, Int> P;
typedef vector<double> vec;
typedef vector<vec> mat;
const int N = 200005;
//////////////////////////////

string s;
int n;
vector<int> dp(N, INF);
vector<int> memo(1 << 26, INF);
int hor(int bit, int i)
{
	return bit ^ (1 << i);
}

void solve()
{
	cin >> s;
	n = s.size();
	dp[0] = 0;
	memo[0] = 0;
	int par = 0;
	RREP(i, n) {
		par = hor (par, s[i - 1] - 'a');
		dp[i] = min(dp[i], memo[par] + 1);
		REP(j, 26) {
			par = hor (par, j);
			dp[i] = min(dp[i], memo[par] + 1);
			par = hor (par, j);
		}
		memo[par] = min(memo[par], dp[i]);
	}
	cout << dp[n] << endl;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);
	solve();
	return 0;
}



Measured memory_bytes: 266588
n = int(input())
nums = [-3, -2, -1, 1, 2, 3]

for i in range(n):
    s = input()
    lst =[]
    for j in range(8):
        lst.append(list(input()))

    X = int(input())
    Y = int(input())
    bomblst = [[X-1, Y-1]]

    for j in bomblst:
        lst[j[1]][j[0]] = '0'
                
        for num in nums:
            kx = [j[0], j[1] + num]
            if 0 <= kx[1] <= 7:
                if lst[kx[1]][kx[0]] == '1':
                    bomblst.append(kx)

            ky = [j[0] + num, j[1]]
            if 0 <= ky[0] <= 7:
                if lst[ky[1]][ky[0]] == '1':
                    bomblst.append(ky)

    print('Data ' + str(i+1) + ':')
    for k in lst:
        print(''.join(k))


Measured memory_bytes: 5724
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1000000007 // 1e9+7
#define PI acos(-1.0)
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1

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

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int x;cin>>x;
  if(x<1200){
    P("ABC");
  }else{
    P("ARC");
  }
  return 0;
}


Measured memory_bytes: 256
C = [list(map(int,input().split())) for _ in range(3)]

ans = 'No'
if C[0][0] - C[1][0] == C[0][1] - C[1][1] == C[0][2] - C[1][2]:
    if C[1][0] - C[2][0] == C[1][1] - C[2][1] == C[1][2] - C[2][2]:
        if C[0][0] - C[0][1] == C[1][0] - C[1][1] == C[2][0] - C[2][1]:
            if C[0][1] - C[0][2] == C[1][1] - C[1][2] == C[2][1] - C[2][2]:
                ans = 'Yes'
print(ans)

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M; cin >> N >> M;
    vector<int> s(M);
    vector<char> c(M);
    for (int i=0;i<M;++i) cin >> s[i] >> c[i];
    for (int i=0;i<1000;++i){
        string S=to_string(i);
        if (S.size()!=N) continue;
        int ok=1;
        for (int j=0;j<M;++j)
            if (S[s[j]-1]!=c[j]) ok=0;
        if (ok){
            cout << i << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
}


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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define fi first
#define se second
#define setpre(x) cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

int main(){
    vector<int> vec;
    int k, n; cin >> k >> n;
    rep(i, n){
        int a; cin >> a;
        vec.push_back(a);
    }
    vec.push_back(vec[0] + k);
    int m = 0;
    rep(i, n){
        m = max(m, vec[i+1] - vec[i]);
    }
    out(k - m);
}

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

using ll=long long; 

void solve(){
	int n;
	cin>>n;
	vector<int>a(n);
	for(int i=0; i<n; i++)cin>>a[i];
	cout<<*max_element(a.begin(), a.end())-*min_element(a.begin(), a.end())<<endl;	
}

signed main(){
	//while(1)
	solve();
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#define ll long long

using namespace std;
int n,m,k,a[300100];
string s;

int main()
{
    int n;
    cin >> n;
    int L = n/100;
    int R = n % 100;
    bool check = false , check2 = false;
    if((R >= 1 && R <= 12))  check = true;
    if((L >= 1 && L <= 12))  check2 = true;
    if(check && check2)
        cout << "AMBIGUOUS";
    else if(check)
        cout << "YYMM";
    else if(check2)
        cout << "MMYY";
    else
        cout << "NA";
    return 0;
}


Measured memory_bytes: 256
h, w = list(map(int, input().split()))
li = []
for _ in range(h):
    li.append(input())

for hh in range(h):
    for ww in range(w):
        if li[hh][ww] == '#':
            print('#', end='')
        else:
            w0 = max(ww - 1, 0)
            w1 = min(ww + 2, w)
            h0 = max(hh - 1, 0)
            h1 = min(hh + 2, h)
            cnt = sum(li[hx][w0: w1].count('#') for hx in range(h0, h1))
            print(cnt, end='')
    print('')

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


typedef long double D;
const D PI = acos(-1.0);
const D EPS = 1e-10;
class P { public:
  D x, y;
  P(D x=0, D y=0) : x(x), y(y) {}

  P& operator+=(const P& o) { x += o.x; y += o.y; return *this; }
  P& operator-=(const P& o) { x -= o.x; y -= o.y; return *this; }
  P& operator*=(const P& o) { return *this = {x*o.x - y*o.y, x*o.y + y*o.x}; }
  P& operator*=(const D& r) { x *= r; y *= r; return *this; }
  P& operator/=(const D& r) { x /= r; y /= r; return *this; }
  P operator-() const { return {-x, -y}; }

  D norm() const { return x*x + y*y; }
  D abs() const { return sqrt(norm()); }
  D arg() const { return atan2(y, x); }
  bool isZero() const { return std::abs(x) < EPS && std::abs(y) < EPS; }
  /** 象限 */
  int orth() const { return y >= 0 ? (x >= 0 ? 1 : 2) : (x < 0 ? 3 : 4); }
  static P polar(const D& rho, const D& theta = 0) { return {rho * cos(theta), rho * sin(theta)}; }
};
std::ostream &operator<<(std::ostream &os, P const &p) { return os << "(" << p.x << ", " << p.y << ")"; }
std::istream &operator>>(std::istream &is, P &p) { D a, b; is >> a >> b; p = P(a, b); return is; }
P operator+(const P& p, const P& q) { return P(p) += q; }
P operator-(const P& p, const P& q) { return P(p) -= q; }
P operator*(const P& p, const P& q) { return P(p) *= q; }
P operator*(const P& p, const D& r) { return P(p) *= r; }
P operator/(const P& p, const D& r) { return P(p) /= r; }
P operator*(const D& r, const P& p) { return P(p) *= r; }
P operator/(const D& r, const P& p) { return P(p) /= r; }
D crs(const P& a, const P& b){ return a.x*b.y - a.y*b.x; }
D dot(const P& a, const P& b){ return a.x*b.x + a.y*b.y; }
int signum(D x) {return x > EPS ? +1 : x < -EPS ? -1 : 0;}
// 辞書順ソート
bool operator<(const P& a, const P& b) {
  if (a.x != b.x) return a.x < b.x;
  return a.y < b.y;
}
// // 偏角ソート
// bool operator<(const P& a, const P& b) {
//   // atan2を使う方法。誤差に注意
//   // return a.arg() < b.arg();

//   // cosを使う方法。(0,0)の扱いに注意
//   if (a.isZero() != b.isZero()) return a.isZero() > b.isZero();
//   if (a.orth() != b.orth()) return a.orth() < b.orth();
//   return crs(a, b) > 0;
// }
/** ベクトルpをベクトルbに射影したベクトル */
P proj(const P& p, const P& b) {
  P t = b * dot(p, b);
  return t / b.norm();
}

int main2() {
  P p1, p2;
  cin >> p1 >> p2;
  P v = p2 - p1;
  int N; cin >> N;
  REP(i, N) {
    P q; cin >> q;
    P ans = proj(q - p1, v) + p1;
    printf("%.12f %.12f\n", (double)ans.x, (double)ans.y);
  }
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}



Measured memory_bytes: 3220
#include <iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); ++i) 

int main() {
	string s, t;
	cin >> s >> t;
	int ans = 0;
	if (s[0] == t[0])ans++;
	if (s[1] == t[1])ans++;
	if (s[2] == t[2])ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include "bits/stdc++.h"

using namespace std;

//------------------------------- Type Names -------------------------------//

using i64 = int_fast64_t;

using seika = string;
//{akari : 1D, yukari : 2D, maki : 3D} vector
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
template <class tsurumaki>
using maki = akari<yukari<tsurumaki>>;
//{akane : ascending order, aoi : decending order} priority queue
template <class kotonoha>
using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;
template <class kotonoha>
using aoi = priority_queue<kotonoha>;

//------------------------------- Libraries ---------------------------------//

//------------------------------- Dubug Functions ---------------------------//

inline void print()
{
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest)
{
    cout << first << ' ';
    print(rest...);
}

//------------------------------- Solver ------------------------------------//

void solve()
{
    seika s;
    cin >> s;
    int L = s.size();
    for (int i = 0; i < L / 2; i++)
    {
        if (s[i] != s[L - i - 1])
        {
            cout << "No" << endl;
            return;
        }
    }
    for (int i = 0; i < L / 4; i++)
    {
        if (s[i] != s[L / 2 - i - 1])
        {
            cout << "No" << endl;
            return;
        }
    }
    for (int i = 0; i < L / 4; i++)
    {
        if (s[i + L / 2 + 1] != s[L - i - 1])
        {
            cout << "No2" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

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


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

signed main() {
  int A,B,C;
  cin >> A >> B >> C;
  int ans = 0;
  while(A != B || B != C || ans%2 != 0){
    ans++;
    if(A<=B && A<=C){
      A++;
    }
    else if(B<=C && B<=A){
      B++;
    }
    else{
      C++;
    }
  }
  cout << ans/2 << endl;
}


Measured memory_bytes: 3568
N, *P = map(int, open(0).read().split())

dp = [0] + [min(i, j, N - 1 - i, N - 1 - j) for i in range(N) for j in range(N)]
memo = [1] * (N * N + 1)

def move(fr, to):
    if dp[to] > dp[fr] + memo[fr]:
        dp[to] = dp[fr] + memo[fr]
        S.append(to)

ans = 0
for p in P:
    ans += dp[p]
    memo[p] = 0

    S = [p]
    while S:
        v = S.pop()

        q, r = divmod(v - 1, N)
        if r != 0:
            move(v, v - 1)
        if r != N - 1:
            move(v, v + 1)
        if q < N - 1:
            move(v, v + N)
        if q >= 1:
            move(v, v - N)

print(ans)

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

using Int = int;
using namespace std;

#define ARC(i, a, b) for(Int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(Int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)
template<class T> T ant(const T &a, const T &b){ return a > b ? a : b; };
template<class T> T ont(const T &a, const T &b){ return a < b ? a : b; };
template<class T> T th(T &a, const T &b, T (*f)(const T &, const T &)){ a = f(a, b); }
#define anth(a, b) th(a, b, ant)
#define onth(a, b) th(a, b, ont)

int main(){
	Int a;
	cin >> a;
	if(a % 2 == 0){
		puts("0.5");
		return 0;
	}
	printf("%.12lf\n", (double) (a / 2 + 1) / a);
	return 0;
}


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

int N, A, B, C, D;
string op[2] = { "-","+" };

int main() {
	cin >> N;
	A = N / 1000;
	B = (N / 100) % 10;
	C = (N / 10) % 10;
	D = N % 10;

	int n = A;
	for (int i = 0; i < 8; i++) {
		if ((i & 1) == 1) n += B;
		else n -= B;
		if ((i & 2) == 2) n += C;
		else n -= C;
		if ((i & 4) == 4) n += D;
		else n -= D;
		if (n == 7) {
			n = i;
			break;
		}
		n = A;
	}

	cout << A << op[n & 1] << B << op[(n & 2)/2] << C << op[(n & 4)/4] << D << "=7" << endl;
}


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

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

    int a, b, c;
    cin >> a >> b >> c;

    cout << a*b/2 << endl;

    return 0;
}

Measured memory_bytes: 3616
a = gets.to_i
b = gets.to_i
c = gets.to_i
d = gets.to_i
e = gets.to_i

ans = 0
temp = 0
[a,b,c,d,e].each do |v|
  i = v % 10
  if i == 0 then
    ans += v
    next
  else
    if temp < 10 - i then
      temp = 10 - i
    end
    ans += v + 10 - i
  end
end

p ans-temp


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e9)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

int main(){
  
  int n,m;
  cin>>n>>m;
  int a[m],b[m];
  bool c[m][n] = {};
  int temp;
  REP(i,m){
    cin>>a[i]>>b[i];
    REP(j,b[i]){
      cin>>temp;
      temp--;
      c[i][temp] = true;
    }
  }
  
  vector<vector<int>> dp(m+1, vector<int>(1<<n, INF));
  dp[0][0] = 0;
  REPP(i,m){
    REP(j,1<<n){
      //i番目の鍵を使う場合
      int temp = j;
      REP(k,n){
        if(c[i-1][k]){//i番目の鍵がk番目の箱を開けられるかどうか
          temp = temp | (1<<k);
        }
      }
      dp[i][temp] = min(dp[i][temp], dp[i-1][j] + a[i-1]);
      //i番目の鍵を使わない場合
      dp[i][j] = min(dp[i][j], dp[i-1][j]);
    }
  }
  
  int ans;
  if(dp[m][(1<<n)-1] == INF){
    ans = -1;
  }else{
    ans = dp[m][(1<<n)-1];
  }
  
  cout<<ans<<endl;
  
    
  return 0;
}

Measured memory_bytes: 16384
#!/usr/bin/env python3
import sys
from bisect import bisect_left

def solve(N: int, X: "List[int]"):
    y = sorted(X)
    b = y[int(N/2)-1]
    a = y[int(N/2)]

    for i in X:
        if(i <= b):
            print(a)
        else:
            print(b)

    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 30840
#include <stdio.h>

int main(void)
{
    size_t n, w;
    scanf("%zu %zu", &n, &w);
    for (size_t i = 0; i < w + 2; ++i) {
        putchar('#');
    }
    putchar('\n');
    for (size_t i = 0; i < n; ++i) {
        char s[w + 1];
        scanf("%s", s);
        printf("#%s#\n", s);
    }
    for (size_t i = 0; i < w + 2; ++i) {
        putchar('#');
    }
    putchar('\n');
    return 0;
}


Measured memory_bytes: 128
using System;
public class program
{
    public static void Main()
    {
        var count = int.Parse(Console.ReadLine());
        string[] line = Console.ReadLine().Split(' ');
        //var k = count - 1;
        string[] answer = new string[count];
        var a = 0;
        var c = "";
      var sum = 0;
        for(var i = 0; i < count; i++)
        {
            a = int.Parse(line[i]) - 1;
            sum = i + 1;
            c = sum.ToString();
            answer[a] = c;
        }
        foreach(var b in answer)
        {
            Console.Write(b + " ");
        }
    }
}

Measured memory_bytes: 27992
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
int getDigit(int n);            // 数字の桁数を取得する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// class
// ------------------------------------------------
class Combi
{
  public:
    Combi();
    long long Combination(long long n, long long k);
    long long nPk_modp(long long n, long long k, long long p);
  private:
    vector<vector<long long>> memo;
    long long n_num;
    long long k_num;
    void Resize(long long n, long long k);
};

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

const int INF = 1e9;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<long> vll;
// code
// ------------------------------------------------
int main() {

    ll n;
    cin >> n;

    ll ans = 0;

    if(n % 2 == 0)
    {
        n /= 2;
        while(n)
        {
            ans += n / 5;
            n /= 5;
        }
    }
    else
    {
        ans = 0;
    }
    
    cout << ans << endl;

    return 0;
}
// funcの実体
// ------------------------------------------------
int getDigit(int n)
{
  int i = 1;
  while(1)
  {
    n = n / 10;
    if(n == 1)
      break;
    i++;
  }
  return i;
}
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Combi::Combi(){
  n_num = -1;
  k_num = -1;
};
ll Combi::Combination(ll n, ll k)
{
  Resize(n,k);

  ll ret;
  if(memo[n][k] != 0)
  {
    ret = memo[n][k];
  }
  else if(n == k || k == 0)
  {
    memo[n][k] = 1;
    ret = 1;
  }
  else
  {
    ret = Combination(n - 1, k - 1) + Combination(n - 1, k);
    memo[n][k] = ret;
  }
  return ret;
}

void Combi::Resize(ll n, ll k)
{
  if(n_num <= n || k_num <= k)
  {
    n_num = (n + 1) * 2;
    k_num = (k + 1) * 2;
    memo.resize(n_num);
    for(auto itr = memo.begin(); itr != memo.end(); ++itr)
    {
      itr->resize(k_num);
    }
  }
}

long long Combi::nPk_modp(long long n, long long k, long long p)
{
  ll ans = 1;
  for(long long i = k; i <= n; i++)
  {
    ans = (ans * i) % p;
  }

  return ans;
};


Measured memory_bytes: 256
n = int(input())
s = {}
for i in range(n):
    temp = input()
    s.setdefault(temp, 0)
    s[temp] += 1
num = max(s.values())
s2 = list(s.items())
s3 = [s2[i][0] for i in range(len(s)) if s2[i][1] == num]
s3.sort()
for i in s3:
    print(i)

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

int main() {
    string s;
    cin >> s;
    ll ans = 0;
    ll n = (ll)s.size();
    for(ll i = 0; i < (ll)(1 << (n - 1)); i++) {
        bitset<11> bi(i);
        if(bi.count() != 3) continue;
        vector<string> v;
        string tmp = "";
        for(ll j = 0; j < n; j++) {
            tmp += s[j];
            if(bi[j]) {
                v.push_back(tmp);
                tmp = "";
            }
        } 
        v.push_back(tmp);
        bool ok = true;
        for(ll j = 0; j < v.size(); j++) {
            if(v[j][0] == '0' && v[j].size() != 1) ok = false;
            if(stol(v[j]) > 256LL) ok = false;
        }
        if(ok) ans++;
     }
     cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3208
/* Alohomora */
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define inp(i,a,n) for(i=0;i<n;i++) {cin>>a[i];}
#define op(i,a,n)  for(i=0;i<n;i++) {cout<<a[i]<<" ";}
#define pb         push_back
#define mp         make_pair
#define F          first 
#define S          second
#define mod        998244353
#define all(x) 	   x.begin(),x.end()	
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
bool compar(const pair<string,ll> &a, const pair<string,ll> &b) 
{ 
    if(a.first==b.first)
    return (a.second < b.second);
    else
    return (a.first < b.first);
}

void comp()
{
	ll i,j,k,m,n,p,w,d,x,y;
	cin>>n>>k;
 	cout<<(n*(n-1))/2+(k*(k-1))/2;

}

int main()
{
    speedup;
    ll i=0,t;
    ll n;
    //cin>>t;
    t=1;
	while(t--)
    {
    	i++;
    	//cout<<"Case #"<<i<<": ";
        comp();
    }
    return 0;
}


Measured memory_bytes: 256
package main

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

func main() {
	K, N := ReadInt(), ReadInt()
	A := ReadInts(N)
	max := 0
	for i := 0; i < N-1; i++ {
		max = Max(max, A[i+1]-A[i])
	}
	max = Max(max, A[0]+K-A[N-1])
	fmt.Println(K - max)
}

func Max(xs ...int) int {
	max := xs[0]
	for _, x := range xs[1:] {
		if max < x {
			max = x
		}
	}
	return max
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 5112
#include<stdio.h>
#include<math.h>

int main(void)
{
	double a=0, b=0, c=0,d=0, s, l, h,PI,rad;

	scanf("%lf %lf %lf", &a, &b, &c);

	PI = acos(-1);

	rad = c*PI / 180;

	s = 0.5*a*b*sin(rad);

	d = sqrt(a*a + b*b - 2 * a*b*cos(rad));

	l = a + b + d;

	h = s * 2 / a;

	printf("%f\n%f\n%f\n", s,l,h);

	return 0;
	
}


Measured memory_bytes: 2100
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(){
  int num,tmp;
 
  cin >> num;

  int a[num][3];


  for(int i=0; i<num; ++i)
    cin >> a[i][0] >> a[i][1] >> a[i][2];


  for(int i=0; i<num; ++i){

    sort(a[i],a[i]+3,greater<int>());
    
    if(a[i][0]*a[i][0] == a[i][1]*a[i][1] + a[i][2]*a[i][2]){
      cout << "YES\n";
    }else{
      cout << "NO\n";
    }
  }  

}

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

int main(){
    int x, y;
    int typea=0, typeb=0, typec=0;
    cin >> x >> y;
    switch(x){
        case 1:
            typea++;
        break;
        case 3:
            typea++;
        break;
        case 5:
            typea++;
        break;
        case 7:
            typea++;
        break;
        case 8:
            typea++;
        break;
        case 10:
            typea++;
        break;
        case 12:
            typea++;
        break;
        case 4:
            typeb++;
        break;
        case 6:
            typeb++;
        break;
        case 9:
            typeb++;
        break;
        case 11:
            typeb++;
        break;
        case 2:
            typec++;
        break;
    };
    switch(y){
        case 1:
            typea++;
        break;
        case 3:
            typea++;
        break;
        case 5:
            typea++;
        break;
        case 7:
            typea++;
        break;
        case 8:
            typea++;
        break;
        case 10:
            typea++;
        break;
        case 12:
            typea++;
        break;
        case 4:
            typeb++;
        break;
        case 6:
            typeb++;
        break;
        case 9:
            typeb++;
        break;
        case 11:
            typeb++;
        break;
        case 2:
            typec++;
        break;
    }
    if(typea==2||typeb==2||typec==2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
s = int(input())
dp = [0] * (s + 11)
mod = 10 ** 9 + 7
dp[0] = 1
dp[1] = 0
dp[2] = 0
dp[3] = 1
c = 2
for i in range(4, s + 1):
    dp[i] = (c - dp[i - 1] - dp[i - 2]) % mod
    c = (c + dp[i]) % mod
print(dp[s])

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

#define vi push_back
#define vo pop_back
#define mp make_pair
#define fe first
#define se second
typedef long long ll;

const int MXN = 1e2 + 10;

int Square[MXN][MXN];
int h, w, n, Colors[MXN * MXN];

void Input () {
    cin >> h >> w >> n;
    for (int i = 0; i < n; i++)
        cin >> Colors[i];
}

void Solve () {
    int clr = 0;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            if (i % 2 == 0)
                Square[i][j] = clr + 1;
            else
                Square[i][w - j - 1] = clr + 1;
            Colors[clr]--;
            if(Colors[clr] == 0)
                clr++;
        }
}

void Output () {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << Square[i][j] << ' ';
        }
        cout << endl;
    }
}

int main () {
    Input();
    Solve();
    Output();
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<int, int>
#define debug(x) cout << #x << ": " << x << ", "
#define debugln(x) cout << #x << ": " << x << '\n'

using namespace std;
using ll = long long;
const int mod = 1e9+7;

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

  int K; cin >> K;
  vector<P> graph[K];

  rep(i, K) {
    graph[i].emplace_back(1, (i+1)%K);
    graph[i].emplace_back(0, (i*10)%K);
  }

  vector<int> d(K);
  priority_queue<P, vector<P>, greater<>> que;

  d.at(1) = 1;
  que.emplace(1, 1);
  while(!que.empty()) {
    P pair = que.top(); que.pop();
    int pos = pair.second;
    int dist = pair.first;
    if (d.at(pos) != 0 && d.at(pos) < dist) continue;
    for (auto e : graph[pos]) {
      int v = e.second;
      int dd = e.first;
      //debug(v); debugln(dd);
      if (d.at(v) != 0 && d.at(v) <= dist + dd) continue;
      d.at(v) = dist + dd;
      que.emplace(d.at(v), v);
    }
  }
  cout << d.at(0) << endl;
}

Measured memory_bytes: 6780
import sys
sys.setrecursionlimit(pow(10, 6))

n = int(input())
nodes = [[] for _ in range(n)]
visited = [False for _ in range(n)]
dist = [0 for _ in range(n)]

def dfs(i, d):
  dist[i] = d
  for cn, c in nodes[i]:
    if not visited[cn]:
      visited[cn] = True
      dfs(cn, d+c)

for _ in range(n-1):
  u, v, w = map(int, input().split())
  nodes[u-1].append((v-1, w))
  nodes[v-1].append((u-1, w))

visited[0] = True
dfs(0, 0)

for c in dist:
  if c % 2 == 0:
    print(0)
  else:
    print(1)


Measured memory_bytes: 82980
#include<bits/stdc++.h>
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define fi first
#define se second
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;

int main(){
    FIO
    int n,r;
    cin>>n>>r;
    if(n>=10)cout<<r;
    else cout<<100*(10-n)+r;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int a,b;
	int sum=0;
	cin>>a>>b;
	if(a==0||b==0)
	{
		cout<<"Zero";
		return 0;
	}
	if(a>0&&b>0)
	{
		cout<<"Positive";
		return 0;
	}
	if(a<0&&b<0)
	{
		sum=abs(a-b)+1;
		if(sum%2==0)
		{
			cout<<"Positive";
			return 0;
		}
		else
		{
			cout<<"Negative";
			return 0;
		}
	}
	if((a>0&&b<0)||(a<0&&b>0))
	{
		cout<<"Zero";
		return 0;
	}
	return 0;
}



Measured memory_bytes: 256
// ConsoleApplication.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include "stdio.h"
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string>
#include <vector>

using namespace std;

void bubbleSort(vector<int>& intArray, int& swapCount)
{
	swapCount = 0;
	bool existsInverseOrderElements = true;
	const int numberOfElements = intArray.size();
	while (existsInverseOrderElements) {
		existsInverseOrderElements = false;
		for (int i = numberOfElements - 1; i != 0; --i) {
			int& front = intArray.at(i - 1);
			int& back = intArray.at(i);
			if (front > back) {
				swap(front, back);
				++swapCount;
				existsInverseOrderElements = true;
			}
		}
	}
}

int main()
{
	int n;
	cin >> n;
	vector<int> intArray(n);
	for (auto& i : intArray) {
		cin >> i;
	}

	int swapCount;
	bubbleSort(intArray, swapCount);
	const string values = accumulate(intArray.begin() + 1, intArray.end(), to_string(intArray.front())
		, [](const string init, const int v) {return init + " " + to_string(v); });
	cout << values << endl;
	cout << swapCount << endl;

	return 0;
}


Measured memory_bytes: 3244
#include<cstdio>
#include<cctype>
#include<vector>
using namespace std;
const int N=1e5;
int n,a[N+1];
vector<int>e[N+1];
int root;
long long f[N+1];
bool res=true;
int read()
{
	int ret=0;
	char c=getchar();
	while(!isdigit(c)) {
		c=getchar();
	}
	while(isdigit(c)) {
		ret=ret*10+c-'0';
		c=getchar();
	}
	return ret;
}
void dfs(int u,int fa)
{
	long long maxf=0,sumf=0;
	for(int v:e[u]) {
		if(v==fa) {
			continue;
		}
		dfs(v,u);
		if(!res) {
			return;
		}
		maxf=max(maxf,f[v]),sumf+=f[v];
	}
	if(e[u].size()==1) {
		f[u]=a[u];
	} else {
		long long x=sumf-a[u],y=2*a[u]-sumf;
		if((x<0)||(y<0)||(x>min(sumf-maxf,sumf/2))||(!fa&&y)) {
			res=false;
		}
		f[u]=y;
	}
	return;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i) {
		a[i]=read();
	}
	for(int i=1,u,v;i<n;++i) {
		u=read(),v=read();
		e[u].push_back(v),e[v].push_back(u);
	}
	if(n==2) {
		res=a[1]==a[2];
	} else {
		for(int i=1;i<=n;++i) {
			if(e[i].size()>1) {
				root=i;
				break;
			}
		}
		dfs(root,0);
	}
	puts(res?"YES":"NO");
	return 0;
}


Measured memory_bytes: 17680
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
int main()
{
    Hello
    int n;
    cin >> n;
    double arr[n + 5];
    priority_queue<double, vector<double>, greater<double>> p;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        p.push(arr[i]);
    }
    while(p.size()){
        if(p.size() == 1)
            return cout << fixed << setprecision(5) << p.top(), 0;
        double a = p.top();
        p.pop();
        double b = p.top();
        p.pop();
        p.push((a + b)/2.0);
    }
    return 0;
}


Measured memory_bytes: 3776
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;
ll prime[1000010];

ll inv(ll x,ll power) {
	ll res = 1;
	ll k = power;
	ll y = x;
	while (k) {
		if (k & 1)res = (res*y) % N;
		y = (y%N*y%N) % N;
		k /= 2;
	}
	return res;
}

int main(void){
    ll n,ans=0;
    cin>>n;
    vector<ll>a(n),b(n);
    map<ll,ll>p;
    ll ma = 0;
    for(ll i=0;i<n;i++){
        cin>>a[i];
        ma=max(ma,a[i]);
    }
    for(ll i=0;i<n;i++){
        ll tmp = a[i];
        for(ll j=2;j*j<=tmp;j++){
            ll num = 0;
            while(tmp%j==0){
                num++;
                tmp/=j;
            }
            if(num!=0)p[j]=max(p[j],num);
        }
        if(tmp>1){
            p[tmp]=max(p[tmp],1LL);
        }
    }
    ll L = 1;
    for(auto itr:p){
        ll now = itr.first;
        ll power =itr.second;
        L = (L*inv(now,power))%N;
    }
    for(ll i=0;i<n;i++){
        ans =(ans+(L*inv(a[i],N-2))%N)%N;
    }
    cout<<ans<<endl;
    return 0;
}

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

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

    if(S[0] == S[1] && S[1] == S[2])
    {
        cout<<"No"<<endl;
        return 0;
    }

    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<queue>

using namespace std;
static const int R =100;
static const int IF = (1<<21);

int num,Mi[R][R],i,x,y;
int D[R];

void BF(int A){
  queue<int> Q;
  Q.push(A);
  for(i = 0;i<num;i++){
    D[i] = IF;
  }
  D[A] = 0;

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

    for(y=0;y<num;y++){
      if(Mi[x][y] == 0){
	continue;
      }
      if(D[y] != IF){
	continue;
	  }
      D[y] = D[x] +1;
      Q.push(y);
    }
  }
  for(i =0; i<num; i++){
    cout << i+1 << " " <<((D[i] ==IF) ? (-1) : D[i]) << endl;
  }
}

  int main(){
    int x,z,y,i,j;

    cin >> num;

    for(i=0;i<num;i++){
      for(j=0;j<num;j++){
	Mi[i][j] = 0;
      }
    }

    for(i = 0;i<num;i++){
      cin >> x >>z;
      x--;

      for(j=0;j<z;j++){
	cin>>y;
	y--;
	Mi[x][y] =1;
      }
    }

    BF(0);

    return 0;
  }
    

      



Measured memory_bytes: 3116
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

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

int main(){
    long int h;
    cin >> h;
    long int num = 1;
    long int ans = 0;
    while(h > 0){
        ans += num;
        num *= 2;
        h /= 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

class UFDS {

public:
	// this function initializes the UFDS
	UFDS(ll n) {
		par.resize(n);
		sz.resize(n);
		for (ll i = 0; i < n; i++) {
			par[i] = i;
			sz[i] = 1;
		}
	}

	//  this function returns the representative of the group that item x is in
	ll find(ll x) {
		if (par[x] == x) {
			return x;
		}
		else {
			// path compression: link x -> representative of the group directly
			// recursively follow the arrows up to the representative
			par[x] = find(par[x]);
			return par[x];
		}
	}

	// this function combines the groups items x and y are in
	void merge(ll x, ll y) {
		// find the representatives of the two groups
		x = find(x);
		y = find(y);
		if (x == y) {
			return;
		}
		par[x] = y; // x -> y
		sz[y] += sz[x]; // number of items in group y has increased by the number of items in group x
		return;
	}

	// this function returns the size of the group item x is in
	ll get_size(ll x) {
		return sz[find(x)];
	}

	// this function returns true if items x and y are in the same set
	bool same_set(ll x, ll y) {
		return find(x) == find(y);
	}

private:
	vector<ll> par;
	// par[i] is the 'parent' of item i
	// i -> par[i]
	vector<ll> sz;
	// sz[i] stores the number of items in group i
};

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

	ll n, m;
	cin >> n >> m;
	UFDS data(n);

	vector<pair<ll, ll>> bridges(m);
	ll ans = (n) * (n - 1) / 2;
	for (int i = 0; i < m; i++) {
		ll x, y;
		cin >> x >> y;
		bridges[i] = make_pair(x - 1, y - 1);
	}
	vector<ll> answers(m);
	for (int i = m - 1; i >= 0; i--) {
		answers[i] = ans;
		//backwards merge
		ll x = bridges[i].first;
		ll y = bridges[i].second;
		if (data.same_set(x, y)) {
			// Do nothing
			continue;
		}
		ll size_x = data.get_size(x);
		ll size_y = data.get_size(y);
		ans += (size_x) * (size_x - 1) / 2;
		ans += (size_y) * (size_y - 1) / 2;
		ll new_sz = size_x + size_y;
		ans -= (new_sz) * (new_sz - 1) / 2;
		data.merge(x, y);
	}
	for (int i = 0; i < m; i++) {
		cout << answers[i] << '\n';
	}
}

Measured memory_bytes: 7136
n,m=map(int,input().split())
n_list=[list(map(int,input().split())) for i in range(n)]
m_list=[list(map(int,input().split())) for i in range(m)]
for i in range(n):
	list=[]
	for j in range(m):
		x=abs(n_list[i][0]-m_list[j][0])
		y=abs(n_list[i][1]-m_list[j][1])
		list.append(x+y)
	print(list.index(min(list))+1)

Measured memory_bytes: 3064
// finish date: 2018/05/26

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define pii pair<int,int>
const int bigmod = 1000000007;
#define INF 1050000000


int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    vi count_W(N, 0);
    vi count_E(N, 0);
    rep(i, N) {
        if (i != 0) {
            count_W[i] += count_W[i - 1];
            count_E[i] += count_E[i - 1];
        }
        if (S[i] == 'W') count_W[i]++;
        else count_E[i]++;
    }
    int mi = INF;
    rep(i, N) {
        if (S[i] == 'W') {
            mi = min(mi, count_W[i] - 1 + count_E[N - 1] - count_E[i]);
        } else {
            mi = min(mi, count_W[i] + count_E[N - 1] - count_E[i]);
        }
    }
    cout << mi << endl;

    return 0;
}




Measured memory_bytes: 3076