akhauriyash/Code-Regression huggingface dataset:
N = 0
def f(x,y,total):
    total = x*4 + y*7

    if total == N:
        print("Yes")
        exit()
    elif total < N:
        f(x+1,y,total)
        f(x,y+1,total)

N = int(input())
f(0,0,0)
print("No")


Measured memory_bytes: 2940
# coding=utf-8

if __name__ == '__main__':
    n, m = [int(s) for s in raw_input().split()]
    a = [raw_input().strip() for row in range(n)]
    b = [raw_input().strip() for row in range(m)]

    for i in range(m):
        if b[i] not in a[i]:
            print('No')
            exit(0)
    else:
        print('Yes')


Measured memory_bytes: 2568
#include<iostream>


using namespace std;
int main()
{  
    int n;
	cin>>n;
	int a[n]={0},input;
	for(int i =0;i<n-1;i++){
		cin>>input;
		a[input-1] += 1; 
	}
	for(int i =0;i<n;i++){
		cout<<a[i]<<endl;
	}
}

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

int main(){
    int flag=1;
    int a,b;
    int ans=0;

    cin >>a>>b;
    if(a*b%2==1)std::cout << "Odd" << '\n';
    else std::cout << "Even" << '\n';
    //cout << ans <<endl;
    //cout <<fixed<<setprecision(16)<< ans <<endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "vector"
#include "string"
#include "map"
#include "algorithm"
#include "functional"
#include "set"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;



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

	cin >> N;
	vector<int>v(N * 2);
	for (auto &i : v)cin >> i;
	sort(v.begin(), v.end());
	int ans = 0;
	for (int i = 0; i < N * 2; i += 2)ans += v[i];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;

alias sread = () => readln.chomp();
alias Point2 = Tuple!(long, "y", long, "x");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void minAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) min(dst, src);
}

void maxAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) max(dst, src);
}

void main()
{
    long D, N;
    scan(D, N);
    if (N == 100)
    {
        switch (D)
        {
        case 0:
            writeln(101);
            return;
        case 1:
            writeln(10100);
            return;
        case 2:
            writeln(1010000);
            return;
        default:
            assert(0);
        }
    }
    else
    {
        switch (D)
        {
        case 0:
            writeln(N);
            return;
        case 1:
            writefln("%d00", N);
            return;
        case 2:
            writefln("%d0000", N);
            return;
        default:
            assert(0);
        }
    }
}


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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    string N;
    cin >> N;
    string t = N;
    reverse(t.begin(), t.end());
    cout << (N == t ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 15;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

int ans[26];

int cnt[26];
char u[1050];
int main() {
	int N, i, j;
	scanf("%d", &N);
	for (i = 0; i < 26; i++) ans[i] = INF;
	while (N--) {
		scanf("%s", u);
		for (i = 0; i < 26; i++) cnt[i] = 0;
		for (i = 0; u[i] != 0; i++) cnt[u[i] - 'a']++;
		for (i = 0; i < 26; i++) ans[i] = min(ans[i], cnt[i]);
	}
	for (i = 0; i < 26; i++) for (j = 0; j < ans[i]; j++) printf("%c", i + 'a');
	return !printf("\n");
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<tuple>
#include<vector>
#include<map>
using namespace std;

int main(void){
  int K;
  cin >> K;
  //偶数の時
  if(K%2 == 0){cout << (K/2)*(K/2) << endl;}
  else{cout << (K/2)*(K/2 + 1) << endl;}
  return 0;
}


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

int main() {
  string s, t;
  cin >> s >> t;
  cout << t + s << endl;
  return 0;
}

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

#define ll long long

int n, D, A;
vector <pair <int, int> > v;
vector <pair <ll, int> > events;
vector <ll> sum;

int main() {
	scanf("%d %d %d", &n, &D, &A);
	for (int i = 0; i < n; ++ i) {
		int X, H; scanf("%d %d", &X, &H);
		v.push_back(make_pair(X, H));
	}
	sort(v.begin(), v.end());
	sum.push_back(0);
	ll ans = 0;
	for (int i = 0; i < n; ++ i) {
		int X = v[i].first, H = v[i].second;
		int p = lower_bound(events.begin(), events.end(), make_pair(1LL * X, 0)) - events.begin();
		ll on = sum.back() - sum[p];
		ll nH = H - on;
		if (nH >= 0) {
			ll tms = (nH + A - 1) / A;
			ans += tms;
			events.push_back(make_pair(X + 2LL * D, tms));
			sum.push_back(sum.back() + tms * A);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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

#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define FOR(i, n, m) for(int (i) = (n); (i) < (m); ++(i))

constexpr int INF = 1e9;
//constexpr ll INF = 1LL<<61;
constexpr ll mod = 1e9+7;


int main(){
  int N, K;
  cin >> N >> K;
  vector<bool> have(N, false);
  REP(i, K){
    int d;
    cin >> d;
    REP(j, d){
      int A;
      cin >> A;
      A--;
      have[A] = true;
    }
  }
  int sum = 0;
  REP(i, N){
    if(have[i]){
      sum++;
    }
  }
  cout << N - sum << endl;
  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
typedef long long LL;
using namespace std;
const int N=20010;
const int M=40000010;
const int inf=0x3f3f3f3f;
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
}
int n,cnt;
int x[N],y[N];
int bgn[N],nxt[M],to[M],E;
int dfn[N],low[N],dfs_time;
int bel[N],st[N],top,in[N];
int scc_cnt;
struct node
{
	int pos,id,type;
	node(){}
	node(int pos,int id,int type):pos(pos),id(id),type(type){}
}a[N];
inline bool operator<(node A,node B){return A.pos<B.pos;}
inline void add_edge(int u,int v)
{
	//printf("%d %d\n",u,v);
	nxt[++E]=bgn[u],bgn[u]=E,to[E]=v;
}
inline void dfs(int u)
{
	dfn[u]=low[u]=++dfs_time;
	in[st[++top]=u]=1;
	for(int v,i=bgn[u];i;i=nxt[i])
	{
		if(!dfn[v=to[i]])
		{
			dfs(v);
			chkmin(dfn[u],low[v]);
		}
		else if(in[v])chkmin(dfn[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		++scc_cnt;
		int x;
		do
		{
			x=st[top--];
			in[x]=0;
			bel[x]=scc_cnt;
		}while(x!=u);
	}
}
inline bool check(int x)
{
	mem(dfn,0);
	mem(bgn,0);
	mem(bel,0);
	E=0;
	scc_cnt=0;
	dfs_time=0;
	int nowl=1,nowr=1;
	For(i,1,cnt)
	{
		while(nowl<cnt&&a[nowl].pos<=a[i].pos-x)nowl++;
		while(nowr<cnt&&a[nowr+1].pos<a[i].pos+x)nowr++;
		For(j,max(i-10,nowl),i)
		if(i!=j)
		{
			add_edge(a[i].id*2+a[i].type,a[j].id*2+(a[j].type^1));
			add_edge(a[j].id*2+a[j].type,a[i].id*2+(a[i].type^1));
		}
		For(j,i,min(i+10,nowr))
		if(i!=j)
		{
			add_edge(a[i].id*2+a[i].type,a[j].id*2+(a[j].type^1));
			add_edge(a[j].id*2+a[j].type,a[i].id*2+(a[i].type^1));
		}
	}
	For(i,1,n)
	{
		if(!dfn[i*2])dfs(i*2);
		if(!dfn[i*2+1])dfs(i*2+1);
	}
	For(i,1,n)if(bel[i*2]==bel[i*2+1])return 0;
	return 1;
}
int main()
{
	read(n);
	int MAX=0;
	For(i,1,n)
	{
		read(x[i]),read(y[i]);
		a[++cnt]=node(x[i],i,0);
		a[++cnt]=node(y[i],i,1);
		chkmax(MAX,x[i]),chkmax(MAX,y[i]);
	}
	sort(a+1,a+cnt+1);
	int l=1,r=MAX/(n-1),ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 12928
/* 2018-01-15-15.08.43 */

#include<bits/stdc++.h>
#define ll long long int
#define N 100010
using namespace std;

int main()
{
    ll i,A[N],n,j;
    scanf("%lld",&n);
    for(i=0;i<n;i++) scanf("%lld",&A[i]);
    if(A[n-1]!=2)
    {
        printf("-1\n");
        return 0;
    }
    ll high=3,low=2;
    for(i=n-2;i>=0;i--)
    {
        ll templow,temphigh;
        templow=low+((A[i]-low%A[i])%A[i]);
        temphigh=high-(high%A[i])+A[i]-1;
        //printf("%lld %lld\n",templow,temphigh);
        if(templow>high || temphigh<low)
        {
            printf("-1\n");
            return 0;
        }
        low=templow,high=temphigh;
    }
    printf("%lld %lld\n",low,high);
    return 0;
}


Measured memory_bytes: 1152
# N = gets.to_i
# A = gets.split(" ").map(&:to_i)
# S = gets.chomp

a = gets.to_i
b = gets.to_i
c = gets.to_i
d = gets.to_i
e = gets.to_i
k = gets.to_i

max = [a, b, c, d, e].max
min = [a, b, c, d, e].min

if max - min > k
  puts ":("
else
  puts "Yay!"
end


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

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}


// 無限大の値
const long long INF = 1LL << 60;

// 入力
int N;
long long h[100010];

// DP テーブル
long long dp[100010];

int main()
{
    // input
    cin >> N;
    for (int i = 0; i < N; i++) cin >> h[i];

    // DP テーブル全体を初期化 (最小化問題なので INF に初期化)
    for (int i = 0; i < 100010; ++i) dp[i] = INF;

    // 初期条件
    dp[0] = 0;


    // ループ
    for (int i = 1; i < N; ++i)
    {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1) chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    // 解を得て出力
    cout << dp[N - 1] << endl;
}


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



int main() {
  string s, t;
  cin >> s >> t;
  int n = s.size();
  string tt = t.erase(n);
  if(s == tt) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

const int MAXN = 55;

int N, x[MAXN], y[MAXN];
int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%d %d", &x[i], &y[i]);

    int res = N;
    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++){
        if(i == j)continue;

        int c = N;
        for(int k = 0; k < N; k++)
        for(int l = 0; l < N; l++){
            if(k == l)continue;
            
            if((x[k] - x[l] == x[i] - x[j]) && (y[k] - y[l] == y[i] - y[j]))c--;
        }
        res = min(res, c);
    }
    printf("%d\n", res);

    return 0;
}


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

using namespace std ;

int a , b ;
const int hell = 1e9 + 7 ;
int fact[1000001];

int binpower(int a, int b){
        int res = 1;
        while(b){
                if(b&1)
                        (res *= a)%=hell;
                b/=2;
                (a*=a)%=hell;
        }
        return res;
}

int modinverse(int n){
        return binpower(n,hell-2);
}

int ncr(int n , int r){
        if(r==0) return 1 ;
        fact[0] = 1;
        for(int i = 1 ; i <= n ; i++ ){
                fact[i] = fact[i-1]*i%hell;
        }
        return ((fact[n]*modinverse(fact[r]))%hell*modinverse(fact[n-r])%hell)%hell;       
}

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

        cin >> a >> b ;

        if((a+b)%3!=0){
                cout << 0 << endl; 
                return 0 ;
        }

        int n = (2*a-b)/3 , m = (2*b-a)/3;

        if(n < 0 or m < 0 ){
                cout << 0 << endl ;
                return 0;
        }
        //cout << n <<' ' << m << endl ;
        cout << ncr(n+m,m) << endl; 
        
         
        return 0;
        
}

Measured memory_bytes: 6400
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;
ll modpow(ll b, ll e ,ll mod) {
	ll ans = 1;
	for (; e; b = b * b % mod, e /= 2)
		if (e & 1) ans = ans * b % mod;
	return ans;
}


int32_t main(){
	double delta;
	double a, b,h, m;
	cin >> a >> b >> h >> m;
	delta = (60.000*h  - 11.00*m) / (2.0000);
	delta = fabs(delta);
	if(delta > 180.0000) delta = 360.0000 - delta;
	double ans = a*a + b*b  - 2.000 * a * b * cos(delta * acos(-1) / (180.000));
	cout << fixed<<setprecision(9) << sqrt(ans) << endl;
}
  // clever stuff:
  // Math -> gcd it all
  // Did u check N=1? Did you switch N,M? io?  
  // overflow? ll x int


Measured memory_bytes: 4224
#include <stdio.h>
#include <string.h>

int main(){
  char s[128];
  scanf("%s", s)+1;
  int len = strlen(s);
  int ans = 0;
  for (int i = 0; i < len / 2; i++) {
    if (s[i] != s[len - 1- i]) ans++;
  }
  printf("%d", ans);
  return 0;
}

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

using namespace std;

int main(){
    int n;
    cin>>n;
    string x;
    cin>>x;
    int d;
    cin>>d;
    vector<bool> a(n,false);
    for (int i = 0; i < n; ++i) {
        if(d<=0)break;
        if(x[i]=='0'){
            x[i]='1';
            --d;
            a[i]=true;
        }
    }
    if(d>0){
        for (int i = n-1; i >=0; --i) {
            if(d<=0)break;
            if(a[i])continue;
            x[i]='0';
            --d;
        }
    }
    cout<<x<<endl;
    return 0;
}


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

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(v) (int) v.size()

int main(){

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

    cout << a * b ;

    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 1e9+7;
const int N=2e5+9;
set<ll>s;
ll k;
void dfs(ll Num)
{
    if (Num==0)
        return;
    if (Num>=1e11)
        return;
    s.insert(Num);
    ll lD = Num%10;
    ll NumA=Num*10+(lD-1);
    ll NumB =Num*10+(lD+1);
    ll NumC=Num*10+lD;
    if (lD==0){
        dfs(NumB);
        dfs(NumC);
    }
    else if(lD==9){
        dfs(NumA);
        dfs(NumC);
    }
    else
    {
        dfs(NumA);
        dfs(NumB);
        dfs(NumC);
    }
}
int main()
{
    FASTINOUT;
    cin>>k;
    for (int i=0;i<=9;i++)
        dfs(i);
    vector<ll>ans(s.begin(),s.end());
    cout<<ans[k-1]<<endl;
    return 0;
}


Measured memory_bytes: 32000
N, M = gets.split.map(&:to_i)
min, max = gets.split.map(&:to_i)

1.upto(M - 1) do
  l, r = gets.split.map(&:to_i)

  min = l if min <= l
  max = r if max >= r
end

ans = max - min + 1
puts  ans.negative? ? 0 : ans

Measured memory_bytes: 1788
#include <stdio.h>
int main(){
  
  int N, b, r, i;
  b = r = 0;
  
  scanf("%d", &N);
  
  char s[N];
  
  scanf("%s", s);
  
  for(i = 0; i < N; ++i){
    if(s[i] == 'B'){
      ++b;
    }
    else if(s[i] == 'R'){
      ++r;
    }
  }
  
  if(b < r){
    printf("Yes\n");
  } else {
    printf("No\n");
  }
  
  return 0;
  
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string x,y;
    cin>>x>>y;
    ll dp[x.size()+1][y.size()+1];
    memset(dp,0,sizeof(dp));
    for(ll i=1;i<=x.size();i++)
    {
     for(ll j=1;j<=y.size();j++)
     {
      if(x[i-1]==y[j-1])
        dp[i][j]=dp[i-1][j-1]+1;
      else 
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
     }
    }
   string ans="";
  ll i=x.size(),j=y.size();
  while(i>=1&&j>=1)
  {
    if(x[i-1]==y[j-1])
    {ans.insert(ans.begin(),y[j-1]);i--;j--;}
    else if (dp[i-1][j] > dp[i][j-1]) 
         i--; 
      else
         j--; 
   }
   cout<<ans;
    return 0;
}


Measured memory_bytes: 73976
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    X = read_int()
    year = 0
    amount = 100
    while amount < X:
        amount = int(amount*1.01)
        year += 1
    return year


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 9176
/*input
4 5
1 2
2 3
2 4
4 1
4 3
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=1005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,y)
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
#define int ll
int32_t main() {
	int n;
	cin>>n;
	int ans = 0;
	vector<int> a(n);
	REP(i,n) cin>>a[i];
	priority_queue<pii, vector<pii>, greater<pii> > q;
	for (int i = 0; i < n; i++) {
		if (i == 0 || i == n - 1 || a[i - 1] == 0 || a[i + 1] == 0) {
			q.push(pii(a[i], i));
		}
	}
	while (q.size()) {
		int t = q.top().second;
		q.pop();
		int p;
		if (t == 0) {
			p = 1;
		}else
		if (t == n - 1) {
			p = n - 2;
		}else{
			if (a[t - 1] == 0) {
				p = t + 1;
			}
			else {
				p = t - 1;
			}
		}
		int m = a[t] / 2;
		a[t] %= 2;
		int tm = min(a[p], a[t]);
		a[p] -= tm;
		a[t] -= tm;
		m += tm;
		if (m) {
			ans += m;
			q.push(pii(a[p], p));
		}
	}
	REP(i,n){
		ans += a[i] / 2;
		a[i] %= 2;
	}
	cout << ans << endl;
 
	return 0;
}


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

int main()
{
    int n;
    std::cin>>n;
    std::vector<int> h(n);
    for(int i=0;i<n;i++)std::cin>>h[i];
    int cnt = 0;
    for(int i=1;i<=101;i++){
        if(h[0]>=i)cnt++;
        for(int j=1;j<n;j++){
            if(h[j]>=i&&h[j-1]<i)cnt++;
        }
    }
    std::cout<<cnt<<std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
	
#define int long long
#define pb push_back
#define ub upper_bound
#define lb upper_bound
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
	
using ll = long long;
const ll INF = LLONG_MAX - 100;
ll mod = 1e9 + 7;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
	
class fact {
public:
	int fmod = 1e9+7;
	vector<int> fac, inv;
	fact (int n, int Mod = 1e9+7) {
		fmod = Mod;
		fac = vector<int>(n,0);
		inv = vector<int>(n,0);
		fac[0] = 1; for (int i = 1; i < n; i++) fac[i] = fac[i-1] * i % fmod;
		for (int i = 0;i < n;i++) inv[i] = fact::POW(fac[i],fmod-2);
	}
	ll nCr(ll n, ll r) {return (fac[n] * inv[r] % fmod) * inv[n-r] % fmod;}
	ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%fmod;}a = a * a%fmod; b >>= 1;}return c;}
};
	
template <class T = ll> T in() {T x; cin >> x; return (x);}
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
void EMP(int x) {cout<<"!!!"<<x<<"!!!"<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return a * b / GCD(a, b);}
ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%mod;}a = a * a%mod; b >>= 1;}return c;}
void PRI(ll n) {bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) {a[i] = 1LL;}for (int i = 2; i < n + 1LL; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}
bool isSqrt(ll a) {return pow(sqrt(a),2) == a ? 1 : 0;}
void YesNo(bool a) {if (a) cout << "Yes"; else cout << "No"; cout << endl;}
void yesno(bool a) {if (a) cout << "yes"; else cout << "no"; cout << endl;}
void YESNO(bool a) {if (a) cout << "YES"; else cout << "NO"; cout << endl;}
	
bool solve() {
	int n,d; cin >> n >> d;
	int ans;
	if (n % (2*d+1) == 0) cout << n / (2*d+1) << endl;
	else cout << n / (2*d+1) + 1 << endl;
}
	
signed main() {
	// cin.tie(0);
	// ios::sync_with_stdio(false);
	solve();
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
vector<vector<ll> >dp(102,vector<ll>(1e5+3,-1));
ll solve(vector<vector<ll> >&v,ll i,ll w)
{
    if(i>=n || w<=0) return 0;
    if(dp[i][w]!=-1) return dp[i][w];
    if(w>=v[i][0])
    {
        return dp[i][w]=max(v[i][1]+solve(v,i+1,w-v[i][0]),solve(v,i+1,w));
    }
    else
    {
        return dp[i][w]=solve(v,i+1,w);
    }
}
int main()
{
    ll w;
    cin>>n>>w;
    vector<vector<ll> >v(n,vector<ll>(2));
    for(ll i=0;i<n;i++)
    {
        cin>>v[i][0]>>v[i][1];
    }
    cout<<solve(v,0,w);

}


Measured memory_bytes: 83812
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for _ in [0]*n]
    for i in [0]*(n-1):
        a,b = map(int,ipt().split())
        way[a-1].append(b-1)
        way[b-1].append(a-1)
    c = [int(i) for i in ipt().split()]
    c.sort(reverse=True)
    ans = [0]*n
    q = queue.Queue()
    ans[0] = c[0]
    ni = 1
    q.put(0)
    sum = 0
    while ni < n:
        qi = q.get()
        for i in way[qi]:
            if ans[i] == 0:
                ans[i] = c[ni]
                sum += c[ni]
                ni += 1
                q.put(i)

    print(sum)
    print(" ".join(map(str,ans)))



    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 6896
#include<iostream>
#include<vector>

int main(){
	int n,m,sum=0;
	std::cin>>n>>m;

	double d = double(1) / double(4 * m);

	std::vector<int> v;
	std::vector<int> p;
	for (int i = 0; i < n; i++) {
		int x;
		std::cin >> x;
		sum += x;
		v.push_back(x);
	}

	for (int i = 0; i < n; i++) {
		if (v[i] >= sum*d) {
			p.push_back(v[i]);
		}
	}
	
	   
	if (p.size() < m) {
		std::cout<<"No"<<std::endl;
		exit(0);
	}
	

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

Measured memory_bytes: 256
def main():
    L, R = map(int, input().split())

    ans = L * R % 2019
    if R - L >= 2019:
        ans = 0
    else:
        for i in range(L, R+1):
            for j in range(i+1, R+1):
                ans = min(ans, i*j % 2019)
    print(ans)


if __name__ == '__main__':
    main()


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

int main(void){
  int n,m;
  while(std::cin >> n >> m && n!=0 && m!=0){
    std::vector<int> veg;
    for(int i=0;i<n;i++){
      int tmp;
      std::cin >> tmp;
      veg.push_back(tmp);
    }
    std::sort(veg.begin(),veg.end(),std::greater<int>());

    int sum =0;
    for(int i=0;i<n;i++){
      if((i+1)%m != 0){
        sum += veg[i];
      }
    }

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



Measured memory_bytes: 3116
#include<cstdio>
#include<complex>
#include<algorithm>
#include<cmath>
using namespace std;
typedef complex<double> P;
const double EPS = 1e-10;
#define EQ(a, b) (abs((a) - (b)) < EPS)

double dot(P a, P b) { return (a.real() * b.real() + a.imag() * b.imag()); }
double det(P a, P b) { return (a.real() * b.imag() - a.imag() * b.real()); }

int n, m, l, x[100], y[100], a[100], r[100];

P p[100][5];
double d[100][100];

double distanceLSP(P a, P b, P c) {
  if (dot(b-a, c-a) < EPS) return abs(c-a);
  if (dot(a-b, c-b) < EPS) return abs(c-b);
  return abs(det(b-a, c-a)) / abs(b-a);
}

bool isIntersectedLS(P a1, P a2, P b1, P b2) {
  if (EQ(det(a1-a2, b1-b2), 0.0)) {
    if (abs(a1-b1) + abs(a2-b1) < abs(a1-a2) + EPS) return true;
    if (abs(a1-b2) + abs(a2-b2) < abs(a1-a2) + EPS) return true;
    return false;
  }
  return (det(a2-a1, b1-a1) * det(a2-a1, b2-a1) < EPS) &&
         (det(b2-b1, a1-b1) * det(b2-b1, a2-b1) < EPS);
}

int main() {
  while (1) {
    scanf("%d%d%d", &n, &m, &l);
    if (n == 0) break;
    for (int i = 0; i < n; i++) scanf("%d%d%d%d", &x[i], &y[i], &a[i], &r[i]);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 5; j++) {
        double S = (double)(a[i] + 72 * j) * M_PI / 180;
        p[i][j] = P(x[i] - r[i] * sin(S), y[i] + r[i] * cos(S));
      }
    }
    for (int i = 0; i < n; i++) d[i][i] = 0.0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < i; j++) {
        double temp = distanceLSP(p[i][0], p[i][2], p[j][0]);
        for (int k = 0; k < 5; k++) {
          for (int z = 0; z < 5; z++) {
            temp = min(temp, distanceLSP(p[i][k], p[i][(k + 2) % 5], p[j][z]));
            temp = min(temp, distanceLSP(p[i][k], p[i][(k + 3) % 5], p[j][z]));
            temp = min(temp, distanceLSP(p[j][k], p[j][(k + 2) % 5], p[i][z]));
            temp = min(temp, distanceLSP(p[j][k], p[j][(k + 3) % 5], p[i][z]));
            if (isIntersectedLS(p[i][k], p[i][(k + 2) % 5], p[j][z], p[j][(z + 2) % 5])) temp = 0.0, k = 5, z = 5;
            if (isIntersectedLS(p[i][k], p[i][(k + 3) % 5], p[j][z], p[j][(z + 2) % 5])) temp = 0.0, k = 5, z = 5;
            if (isIntersectedLS(p[i][k], p[i][(k + 2) % 5], p[j][z], p[j][(z + 3) % 5])) temp = 0.0, k = 5, z = 5;
            if (isIntersectedLS(p[i][k], p[i][(k + 3) % 5], p[j][z], p[j][(z + 3) % 5])) temp = 0.0, k = 5, z = 5;
          }
        }
        d[i][j] = d[j][i] = temp;
      }
    }
    for (int k = 0; k < n; k++)
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    printf("%.9f\n", d[m-1][l-1]);
  }
}



Measured memory_bytes: 3228
def main():
    def dijkstra_back(s,t):
        prev = [s] * n
        d = [float("inf")] * n
        used = [False] * n
        d[s] = 0
        while True:
            v = -1
            for i in range(n):
                if (not used[i]) and (v == -1):
                   v = i
                elif (not used[i]) and d[i] < d[v]:
                    v = i
            if v == -1:
                   break
            used[v] = True
            for i in range(n):
                if d[i] > d[v] + cost[v][i]: 
                    d[i] = d[v] + cost[v][i]
                    prev[i] = v
        path = [t]
        while prev[t] != s:
            path.append(prev[t])
            prev[t] = prev[prev[t]]
        path.append(s)
        path = path[::-1]
        return path
    
    n,m = map(int,input().split())
    route = [tuple(map(int,input().split())) for _ in range(m)]
    INF = float('inf')
    cost = [[INF for i in range(n)] for i in range(n)] 
    for i in route:
        cost[i[0]-1][i[1]-1] = i[2]
        cost[i[1]-1][i[0]-1] = i[2]
    
    used_ways = set([])
    for i in range(n):
        for j in range(n):
            if i < j:
                way = dijkstra_back(i,j)
                for k in range(len(way)-1):
                    used_ways.add(tuple(sorted([way[k],way[k+1]])))
    route_set = set([])
    for i in route:
        route_set.add(tuple(sorted([i[0]-1,i[1]-1])))
    print(len(route_set-used_ways))

if __name__ == '__main__':
    main()

Measured memory_bytes: 48900
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

// (0,0) -> (x,y)
// k=|dx|+|dy|
// nk>=x+y && nk&1=(x+y)&1

typedef long long LL;
typedef pair<int,int> PII;

int rx=0,ry=0,rxy=0;

inline void print(int x,int y)
{
	//cout<<x<<" "<<y<<endl;
	if(rxy) swap(x,y);
	if(rx) x=-x;
	if(ry) y=-y;
	printf("%d %d\n",x,y);
}

vector<PII> ans;
int nx,ny;
void move(int dx,int dy)
{
	nx+=dx; ny+=dy;
	ans.emplace_back(nx,ny);
}

int main()
{
	int k;
	int x,y;
	scanf("%d%d%d",&k,&x,&y);
	if(x<0)
	{
		rx=1;
		x=-x;
	}
	if(y<0) 
	{
		ry=1;
		y=-y;
	}
	if(x<y)
	{
		rxy=1;
		swap(x,y);
	}
	if(((x+y)&1) && (k&1)==0)
	{
		printf("-1\n");
		return 0;
	}
	//cout<<x<<" "<<y<<" "<<rx<<" "<<ry<<" "<<rxy<<endl;
	int n=(x+y+k-1)/k;
	//if(((k-(x+y)%k)%k)&1) n++;
	if((n&k&1)!=((x+y)&1)) n++;
	if(x+y<k) n=2;
	nx=0; ny=0;
	if(((x+y)&1)&&(x+y<k))
	{
		int a=k-x;
		int b=x+(k+x-y)/2;
		int c=k-x+y;
		int d=(k+x-y)/2;
		while(a>=k)
		{
			move(0,-k);
			a-=k;
		}
		while(a+b>=k)
		{
			if(a)
			{
				move(k-a,-a);
				b-=k-a;
				a=0;
			}
			else
			{
				move(k,0);
				b-=k;
			}
		}
		while(b+c>=k)
		{
			if(b)
			{
				move(b,k-b);
				c-=k-b;
				b=0;
			}
			else
			{
				move(0,k);
				c-=k;
			}
		}
		while(c+d>=k)
		{
			if(c)
			{
				move(-(k-c),c);
				d-=k-c;
				c=0;
			}
			else
			{
				move(-k,0);
				d-=k;
			}
		}
	}
	else
	{
		int a=((LL)k*n-x-y)/2;
		int b=x;
		int c=((LL)k*n-x+y)/2;
		while(a>=k)
		{
			move(0,-k);
			a-=k;
		}
		while(a+b>=k)
		{
			if(a)
			{
				move(k-a,-a);
				b-=k-a;
				a=0;
			}
			else
			{
				move(k,0);
				b-=k;
			}
		}
		while(b+c>=k)
		{
			if(b)
			{
				move(b,k-b);
				c-=k-b;
				b=0;
			}
			else
			{
				move(0,k);
				c-=k;
			}
		}
	}
	printf("%d\n",ans.size());
	for(int i=0;i<(int)ans.size();i++)
		print(ans[i].first,ans[i].second);

	return 0;
}

Measured memory_bytes: 3952
#include <iostream>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

int h, w;

pair<int, int> next_pos(pair<int, int> c) {
    if (c.first % 2 == 1) {
        if (c.second == 0) return make_pair(c.first + 1, 0);
        else return make_pair(c.first, c.second - 1);
    } else {
        if (c.second == w - 1) return make_pair(c.first + 1, w - 1);
        else return make_pair(c.first, c.second + 1);
    }
}

int main() {
    int n, a, m[100][100];
    pair<int, int> p = make_pair(0, 0);
    cin >> h >> w >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        for (int j = 0; j < a; j++) {
            m[p.first][p.second] = i + 1;
            p = next_pos(p);
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w - 1; j++) cout << m[i][j] << " ";
        cout << m[i][w - 1] << endl;
    }
}

Measured memory_bytes: 384
n = int(input())
A = list(map(int, input().split()))
avg = sum(A)//n
avg2 = sum(A)//n + 1
ans = 0
ans2 = 0
for i in A:
    ans += (i-avg)**2
    ans2 += (i-avg2)**2
print(min(ans, ans2))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define meow(args...) fprintf(stderr, args)
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
int (*rd)()=read<int>;

const int N=1e5+10;
int n, deg[N], dis[N], maxdis, choice;
char s[N];
bool del[N];
std::vector<int> edge[N];
void dfs(int u, int d) {
	dis[u]=d+=s[u];
	if(cmax(maxdis, dis[u])) choice=u;
	del[u]=true;
	for(int v: edge[u]) if(!del[v]) dfs(v, d);
	del[u]=false;
}
int main() {
	std::queue<int> q;
	n=rd();
	for(int i=1; i<n; ++i) {
		int u=rd(), v=rd();
		edge[u].push_back(v);
		edge[v].push_back(u);
		++deg[u], ++deg[v];
	}
	assert(scanf("%s", s+1)==1);
	for(int i=1; i<=n; ++i) s[i]=(s[i]=='W');
	int any=std::find(s+1, s+n+1, 1)-s;
	if(any>n) {
		puts("0");
		return 0;
	}
	if(std::count(s+1, s+n+1, 1)==1) {
		puts("1");
		return 0;
	}
	for(int i=1; i<=n; ++i) if(deg[i]==1&&!s[i]) q.push(i);
	while(!q.empty()) {
		int u=q.front(), v;
		q.pop();
		for(v=0; del[edge[u][v]]; ++v);
		v=edge[u][v];
		del[u]=true;
		if(--deg[v]==1&&!s[v]) q.push(v);
	}
	int ans=-2;
	for(int i=1; i<=n; ++i)
		if(!del[i]) {
			s[i]^=deg[i]&1;
			ans+=2+s[i];
			if(deg[i]!=1) s[i]*=2;
		}
	maxdis=-1;
	dfs(any, 0);
	maxdis=-1;
	dfs(choice, 0);
	printf("%d\n", ans-maxdis-maxdis%2);
	return 0;
}


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

namespace easy_Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            string S2 = S.Replace("2017","2018");
            Console.WriteLine(S2);
        }   
            // float[] ABN = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // long[] NK = Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            // long N = NK[0];
            // long K = NK[1];
            // long K = long.Parse(Console.ReadLine());
            // int[] abc = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            // string S = Console.ReadLine();
            // int x = int.Parse(Console.ReadLine());
            // int b = int.Parse(Console.ReadLine());
            // int N = int.Parse(Console.ReadLine());
            // float N = float.Parse(Console.ReadLine());
            // string c = Console.ReadLine();
            // string B = Console.ReadLine();
            // string[] s = Console.ReadLine().Split();
            // var s = (new string[] { Console.ReadLine(), Console.ReadLine(), Console.ReadLine() }).Select(float.Parse);
            // float[] a = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // var X = Console.ReadLine();
            // int[,] abcd = new int[NMQ[2],4];
            // int[] A = new int[NMQ[0]];
            // int[] A_num = new int[NMQ[0]];
            // long[] s=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            // var hs=new Dictionary<long,long>();
            // for(int i=0;i<s[0];i++){
            //     long[] q=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            //     if(hs.ContainsKey(q[0])){hs[q[0]]+=q[1];}
            //     else{hs.Add(q[0],q[1]);}
            // }
        
        // //最小公倍数
        // static long Lcm(long a, long b)
        // {
        //     return a/Gcd(a,b)*b;
        // }

        // //最大公約数
        // static long Gcd(long m, long n)
        // {
        //     if(n==0)return m;
        //     return Gcd(n,m%n);
        // }
    }
}


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

int main(){
  int n,c,k; cin>>n>>c>>k;
  vector<int> t(n);
  for(int i=0; i<n; ++i)cin>>t[i];

  sort(t.begin(),t.end());
  int ans=1, l=t[0]+k, num=1;
  for(int i=1; i<n; ++i){
    if(t[i]<=l && l<=t[i]+k && num<c)++num;
    else{++ans; l=t[i]+k; num=1;}
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define Size 1100000
typedef long long lli;
vector<lli> pri((Size >> 6) + 5), prime;
#define setBits(n) (pri[n >> 6] |= (1 << ((n >> 1) & 31)))
#define checkBit(n) (pri[n >> 6] & (1 << ((n >> 1) & 31)))
#define isP(n) ((n == 2) || (n > 1 && (n & 1) && !checkBit(n)))
void seive()
{
    unsigned i, j;
    for (i = 3; i * i <= Size; i += 2)
        if (!checkBit(i))
        {
            for (j = i * i; j < Size; j += (i << 1))
                setBits(j);
        }
    prime.push_back(2);
    for (i = 3; i < Size; i += 2)
        if (!checkBit(i))
            prime.push_back(i);
}
long long solve()
{
    long long N;
    cin >> N;
    long long last = N + 1;
    for (auto it : prime)
    {
        if (N % it == 0)
        {
            for (long long i = it; i * i <= N; i++)
            {
                if (N % i == 0)
                    last = min(last, i + N / i);
            }
        }
    }
    return last - 2;
}
int main()
{
    // freopen("sample_input.txt", "r", stdin);
    // freopen("sample_output.txt", "w", stdout);
    seive();
    reverse(prime.begin(), prime.end());
    // int test;
    // cin>>test;
    // for(int t=1; t<=test; t++)
    cout << solve() << endl;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

int32 N, M;
vector<int64> G[112345], rG[112345];
vector<int64> ord;
bool visited[112345] = {};
int64 memo[112345] = {};

void dfs(int32 v){
	if (!visited[v]){
		visited[v] = 1;
		REP(i, G[v].size()){
			dfs(G[v][i]);
		}
		ord.push_back(v);
	}
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N >> M;
	REP(i, N+M-1){
		int32 a, b;
		cin >> a >> b; a--; b--;
		G[a].push_back(b);
		rG[b].push_back(a);
	}
	REP(i, N){
		dfs(i);
	}
	reverse(all(ord));
	vector<int64> res(N);
	res[ord[0]] = 0;
	memset(memo, -1, sizeof memo);
	memo[ord[0]] = 0;
	FOR(i, 1, N){
		int32 v = ord[i];
		int32 u = -1;
		REP(j, rG[v].size()){
			if (memo[rG[v][j]] >= 0){
				if (u == -1 || memo[rG[v][j]] > memo[u])
					u = rG[v][j];
			}
		}
		res[v] = u+1;
		memo[v] = i;
	}
	REP(i, N)
		cout << res[i] << endl;
}


Measured memory_bytes: 17144
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

struct mat{
	lint a[3][3];
	mat(int x){
		memset(a, 0, sizeof(a));
	}
	mat(vector<vector<int>> v){
		for(int i=0; i<3; i++){
			for(int j=0; j<3; j++){
				a[i][j] = v[i][j];
			}
		}
	}
};

mat mul(mat a, mat b){
	mat c(0);
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			for(int k=0; k<3; k++){
				c.a[i][j] += a.a[i][k] * b.a[k][j];
			}
			c.a[i][j] %= mod;
		}
	}
	return c;
}

mat ipow(mat a, int p){
	mat ret({{1, 0, 0}, {0, 1, 0}, {0, 0, 1}});
	mat piv = a;
	while(p){
		if(p&1) ret = mul(ret, piv);
		piv = mul(piv, piv);
		p >>= 1;
	}
	return ret;
}

int n, m;

int main(){
	scanf("%d %d",&n,&m);
	mat YC({{1, 0, 0}, {2, 1, 0}, {1, 1, 1}});
	mat NC({{1, 0, 1}, {2, 1, 2}, {1, 1, 2}});
	mat ans = YC;
	int prv = 1;
	while(m--){
		int x;
		scanf("%d",&x);
		ans = mul(ipow(NC, x - prv), ans);
		ans = mul(YC, ans);
		prv = x + 1;
	}
	ans = mul(ipow(NC, n - prv), ans);
	cout << ans.a[2][0];
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <tuple>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
const int INF = 1000000000;
const int MOD = 1000000007;
int main(){
	int n;
	cin >> n;
	vector<ll> a(n);
	for(int i = 0;i < n;i++)cin >> a[i];

	ll ans = 0;
	for(int i = 1;i < n;i++){
		if(a[i] < a[i-1]){
			ans += a[i-1] - a[i];
			a[i] = a[i-1];
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
int n,x,pre,eg,ans,cnt,hd[MAXN],vis[MAXN],in[MAXN],tmp[MAXN],ver[2*MAXN],nx[2*MAXN];
queue <int> q;
int hs (int x,int y) {
	if (x>y) {swap(x,y);}
	return (x-1)*n+y;
}
void add_edge (int x,int y) {
	ver[++eg]=y;
	nx[eg]=hd[x];
	hd[x]=eg;
	in[y]++;
	return;
}
int main () {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n-1;j++) {
			scanf("%d",&x);
			if (j>1) {add_edge(hs(i,pre),hs(i,x));}
			pre=x;
		}
	}
	for (int i=1;i<=MAXN-10;i++) {
		if (!in[i]) {cnt++,q.push(i);}
	}
	while (!q.empty()) {
		int cur=0;
		while (!q.empty()) {
			tmp[++cur]=q.front();
			q.pop();
		}
		for (int i=1;i<=cur;i++) {
			for (int j=hd[tmp[i]];j;j=nx[j]) {
				if (--in[ver[j]]==0) {
					q.push(ver[j]);
					cnt++;
				}
			}
		}
		ans++;
	}
	if (cnt!=MAXN-10) {printf("-1\n");} 
	else {printf("%d\n",ans);}
	return 0;
}

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

int main(void) {
  int n;
  cin >> n;
  vector<pair<int, int>> a(n);
  rep(i, n) cin >> a[i].first >> a[i].second;
  rep(i, n - 2) {
    if (a[i].first == a[i].second && a[i + 1].first == a[i + 1].second &&
        a[i + 2].first == a[i + 2].second) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

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

int main(){
  string s;
  cin >> s;
  for (int i =0; i < s.size();i++){
    if (!(i & 1) && s[i] == 'L'){
      cout << "No" << endl;
      return 0;
    }
    else if ((i & 1) && s[i] == 'R'){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

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

int main(){
  int n,k;
  cin>>n>>k;
  int l[60];
  for(int i=0;i<n;i++)cin>>l[i];
  sort(l,l+n,greater<int>());
  int sum;
  for(int i=0;i<k;i++){
    sum+=l[i];
  }
  cout<<sum<<endl;
}


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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int p[101010];
vector<int> g[101010];
bitset<101010> flag;

void dfs(int v, vector<int>& num, vector<int>& pos) {
    flag[v] = 1;
    pos.push_back(v+1);
    num.push_back(p[v]);
    for (int& u : g[v]) {
        if (flag[u]) continue;
        dfs(u, num, pos);
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    rep(i, N) cin >> p[i];
    rep(i, M) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int ans = 0;
    rep(i, N) {
        vector<int> n, p;
        if (!flag[i]) dfs(i, n, p);
        sort(n.begin(), n.end());
        sort(p.begin(), p.end());
        int idx1=0, idx2=0;
        while (true) {
            if (idx1 >= n.size() or idx2 >= p.size()) break;
            if (n[idx1] == p[idx2]) {
                idx1++; idx2++;
                ans++;
            }
            else if (n[idx1] > p[idx2]) {
                idx2++;
            }
            else if (n[idx1] < p[idx2]) {
                idx1++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 11052
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

int main() {
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  if(n%2==0){
    for(int i=n-1;i>=1;i-=2){
      cout<<a[i]<<' ';
    }
    for(int i=0;i<=n-2;i+=2){
      cout<<a[i];
      if(i!=n-2) cout<<' ';
    }
    cout<<endl;
  }
  else{
    for(int i=n-1;i>=0;i-=2){
      cout<<a[i]<<' ';
    }
    for(int i=1;i<=n-2;i+=2){
      cout<<a[i];
      if(i!=n-2) cout<<' ';
    }
    cout<<endl;
  }
  return 0;
}


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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
const ll MOD = 1000000007;

const int MAX = 2000005;
ll modFact[MAX];
ll modInv[MAX];
ll modFactInv[MAX];

// calc nCr % mod
ll comb(int n, int r) {
  return modFact[n] * (modFactInv[r] * modFactInv[n - r] % MOD) % MOD;
}

void init() {
  modFact[0] = modFact[1] = 1;
  modFactInv[0] = modFactInv[1] = 1;
  modInv[1] = 1;
  REP(i, 2, MAX) {
    modFact[i] = modFact[i - 1] * i % MOD;
    modInv[i] = MOD - modInv[MOD % i] * (MOD / i) % MOD;
    modFactInv[i] = modFactInv[i - 1] * modInv[i] % MOD;
  }
}

int main() {
  init();

  int n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  sort(all(a));

  ll ans = 0;
  rep(i, n) {
    int j = n - i - 1;
    if (j < k - 1) break;
    ans = (ans + MOD + a[n - 1 - i] * comb(j, k - 1) % MOD) % MOD;
    ans = (ans + MOD - a[i] * comb(j, k - 1) % MOD) % MOD;
  }

  cout << ans << endl;
}


Measured memory_bytes: 47872
#pragma GCC optimize(s)
#include <stdio.h>
int math[]={-1,1};
int main()
{
	int a[4];register int i,j,k;
	for(i=0; i<4; ++i)
	{
		char c=getchar();
		a[i]=c-'0';
	}
	for (i=0; i<2; ++i)
		for (j=0; j<2; ++j)
			for (k=0; k<2; ++k)
				if(a[0]+math[i]*a[1]+math[j]*a[2]+math[k]*a[3]==7)
				{
					printf("%d",a[0]);
					printf("%c",i==0?'-':'+');
					printf("%d",a[1]);
					printf("%c",j==0?'-':'+');
					printf("%d",a[2]);
					printf("%c",k==0?'-':'+');
					printf("%d",a[3]);
					printf("=7\n");
					return 0;
				}
}


Measured memory_bytes: 128