akhauriyash/Code-Regression huggingface dataset:
#input
#A = int(input())
#B = int(input())
#C = int(input())
#X = int(input())
#A = list(map(int,input().split()))
#b = int(input())
N,A,B = map(int,input().split())

#s = [0,0,0]
#s[0] = int(input/100)
#s[1] = int(input/10 - s[0]*10)
#[2] = int(input%10)



sum = 0
temp=0
tempy=0
#flag = 0

for i in range(1, N+1): #loop for N
  
  result = 0
  temp = i
  
  while(1):
    result += (int)(temp%10)
    tempy = (int)(temp/10)
    if tempy==0:
      break
    else:
      temp = tempy
  
  if (result >= A) and (result <= B):
    sum += i
    #print(i)
  
  #####
  #revB
  #####
  #p = i%10 #1桁目
  #tempy = (int)(i/10)
  #
  #if tempy > 0:
  #  q = tempy%10 #2桁目
  #  temp = (int)(tempy/10)
  #  tempy = temp
  #else:
  #  q=0
  #  r=0
  #  s=0
 # 
  #if tempy > 0:
  #  r = tempy%10 #3桁目
  # temp = (int)(tempy/10)
  #  tempy = temp
  #else:
  #  r=0
  #  s=0
  
  #if tempy > 0:
  #  s = tempy%10 #4桁目
  #else:
  #  s=0
  
  #####
  #revA
  #####
  #s = (int)(i/1000)
  #r = (int)(i/100-10*s)
  #q = (int)(i/10-10*r-100*s)
  #p = (int)(i%10)
  #print(p)
  #print(q)
  #print(r)
  #print(s)
  
  #temp = p+q+r+s
  #if (temp >= A) and (temp <= B):
  #  sum += i
  #  print(i)

  
#judge

#print('result')
#print(A)
print(sum)


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

using namespace std;

const int maxn = 5100;
const int base = (int)1e9+7;

int n,m,ans,a[maxn],f[2][maxn],sz[maxn],C[maxn][maxn],fact[maxn];
vector<int> g[maxn];

int add(int x,int y) {
    return (x+y)%base;
}

int sub(int x,int y) {
    return (x-y+base)%base;
}

int mult(int x,int y) {
    return ((ll)x*y)%base;
}

void init() {
    for (int i=1;i<=maxn;i++) {
        C[i][i] = 1;
        C[0][i] = 1;
    }
    for (int i=1;i<=maxn;i++)
        for (int j=1;j<i;j++)
            C[j][i] = add(C[j-1][i-1],C[j][i-1]);
    fact[0]=1;
    for (int i=1;i<=maxn;i++) fact[i] = mult(fact[i-1],i);
    //cout<<fact[0]<<endl;
}

void visit(int u,int pa) {
    sz[u]=1;
    for (int j=0;j<g[u].size();j++) {
        int v=g[u][j];
        if (v!=pa) {
            visit(v,u);
            sz[u]+=sz[v];
        }
    }
}

void progress() {
    int t=0;
    f[1-t][0]=1;
    for (int i=1;i<=m;i++) {
        for (int j=0;j<n;j++) f[t][j]=0;
        for (int k1=0;k1<n;k1++)
            for (int k2=0;k2<=a[i];k2++)
                if (k1+k2<n) {
                    f[t][k1+k2] = add(f[t][k1+k2],mult(f[1-t][k1],mult(fact[k2],mult(C[k2][a[i]],C[k2][a[i]]))));
                }
        //for (int j=0;j<=n;j++) cout<<f[t][j]<<" ";
        //cout<<endl;
        t=1-t;
    }
    for (int k=0;k<=n;k++) {
        int val = mult(f[1-t][k],fact[n-k]);
       // cout<<val<<endl;
        if (k%2) ans = sub(ans,val);
        else ans = add(ans,val);
    }
    cout<<ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("in.txt","r",stdin);
    init();
    cin>>n;
    for (int i=1;i<n;i++) {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    visit(1,-1);
    int c=1;
    int old=c;
    while (true) {
       // cout<<c<<" "<<old<<endl;
        old=c;
        for (int j=0;j<g[c].size();j++) {
            int v=g[c][j];
            if (2*sz[v]>=n && sz[v]<sz[old]) {
                old=c;
                c=v;
            }
        }
        if (old==c) break;
    }
    //cout<<c<<endl;
    if (sz[c]==n/2) {
        cout<<mult(fact[sz[c]],fact[sz[c]]);
        return 0;
    }
    visit(c,-1);
    for (int j=0;j<g[c].size();j++) {
        int v=g[c][j];
        a[++m]=sz[v];
       // cout<<m<<" "<<a[m]<<endl;
    }
    progress();
}


Measured memory_bytes: 101376
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<cmath>

using namespace std;

int main()
{
	string S;
	cin >> S;
	
	int ans = 0;
	for (int i = 0; i < 4; i++)
	{
		if (S[i] == '+')
			ans++;
		else
			ans--;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
    int H,W;
    
 while(1){
    scanf("%d %d",&H,&W);
    if(H==0 && W==0)break;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            printf("#");
        }
        printf("\n");
    }
    printf("\n");
 }
}


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

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

set<int> primes(int n){
    vector<bool> a(n+1, 1);
    set<int> st;
    FOR(x,2,n){
        if (!a[x]) continue;
        st.insert(x);
        for (int y = 2 * x; y <= n; y += x) a[y] = 0;
    }
    return st;
}

int main() {
    int m = 1e5 + 10;
    set<int> pri = primes(m);
    VI a(m);
    REP(i,m){
        if (i % 2 == 0 || pri.count(i) == 0) continue;
        if (pri.count((i+1)/2)) a[i] = 1;
    }
    VI s(m);
    REP(i,m-1) s[i+1] = s[i] + a[i];

    int q;
    cin >> q;
    while (q--){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", s[r+1] - s[l]);
    }
    return 0;
}





Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fr first
#define sc second
#define ll  long long
#define mp make_pair
#define mod 1000000007

using namespace std;

int dp[100100];
int dp1[100100];
int dp2[100100];
int dp3[100100];

char s[100100];
char s1[100100];
int main(){
    scanf("%s",s);
    scanf("%s",s1);
    int n = strlen(s);
    int m = strlen(s1);

    for(int i=1;i <=n ;i ++){
       dp[i] = dp[i-1] + (s[i-1] == 'A');
       dp1[i] = dp1[i-1] + (s[i-1] == 'B');
    }

    for(int i=1;i <=m ;i ++){
       dp2[i] = dp2[i-1] + (s1[i-1] == 'A');
       dp3[i] = dp3[i-1] + (s1[i-1] == 'B');
    }

    int q;
    cin>>q;
    int l,r;
    int l1,r1;
    while(q--){
        scanf("%d%d%d%d",&l,&r,&l1,&r1);
        int t = 0;
        int t1 = 0;
        if(dp[r] - dp[l-1] > dp1[r] - dp1[l-1]){
            int k = dp[r] - dp[l-1] -( dp1[r] - dp1[l-1]);
            if(k%3 == 0)
                t = 0;
            else if(k%3 == 1)
                t = 1;
            else
                t = 2;
        }
        else if(dp[r] - dp[l-1] < dp1[r] - dp1[l-1]){
            int k = dp1[r] - dp1[l-1] -( dp[r] - dp[l-1]);
            if(k%3 == 0)
                t = 0;
            else if(k%3 == 1)
                t = 2;
            else
                t = 1;
        }
        l = l1;
        r = r1;
        if(dp2[r] - dp2[l-1] > dp3[r] - dp3[l-1]){
            int k = dp2[r] - dp2[l-1] -( dp3[r] - dp3[l-1]);
            if(k%3 == 0)
                t1 = 0;
            else if(k%3 == 1)
                t1 = 1;
            else
                t1 = 2;
        }
        else if(dp2[r] - dp2[l-1] < dp3[r] - dp3[l-1]){
            int k = dp3[r] - dp3[l-1] -( dp2[r] - dp2[l-1]);
            if(k%3 == 0)
                t1 = 0;
            else if(k%3 == 1)
                t1 = 2;
            else
                t1 = 1;
        }
        if(t == t1){
            printf("YES\n");
        }
        else
            printf("NO\n");
    }

    return 0;
}


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

int main()
{
  int H,N,A,B;
  cin >> H >> N;
  vector<int> dp(H+1,100000001);
  dp[0] = 0;
  for(int n=0; n<N; n++){
    cin >> A >> B;
    for(int h=1; h<H+1; h++){
      dp[h] = min(dp[h],dp[max(0,h-A)]+B);
    }
  }
  cout << dp[H] << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3


mod = 10 ** 9 + 7


def main():
    n = int(input())

    dp = [0 for i in range(n + 1)]

    if n == 1 or n == 2:
        print(0)
        return
    elif n in (3, 4, 5):
        print(1)
        return

    dp[3] = 1
    dp[4] = 1
    dp[5] = 1
    dp[6] = 2
    for i in range(7, n + 1):
        dp[i] += 1
        for j in range(3, i - 2):
            dp[i] += dp[j] % mod

    print(dp[n] % mod)


main()



Measured memory_bytes: 9220
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
int INF = numeric_limits<int>::max() / 2;
ll LINF = numeric_limits<ll>::max() / 2;
int MOD = 1e9 + 7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int ret = INF;
    int n = s.size();
    vector<int> sint(n);
    for(int i = 0; i < n; i++){
        sint[i] = s[i] - 'a';
    }
    for(int ch = 0; ch < 26; ch++){
        int tans = n;
        vector<int> tsint = sint;
        for(int ans = 0; ans < n; ans++){
            bool f = true;
            for(int j = 0; j < tsint.size(); j++){
                if(tsint[j] != ch) f = false;
            }
            if(f){
                tans = ans;
                break;
            }

            vector<int> ttsint(tsint.size()-1, '-');
            for(int j = 0; j < ttsint.size(); j++){
                if(tsint[j] == ch || tsint[j+1] == ch) ttsint[j] = ch;
            }
            tsint = ttsint;
        }
        ret = min(ret, tans);
    }
    cout << ret << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

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

ll gcd(ll a, ll b, ll c){
  return gcd(a, gcd(b, c));
}


int main(void){
  ll k;
  cin >> k;
  

  ll res = 0;
  for (int i = 0; i < k; i++){
    for (int j = 0; j < k; j++){
      for (int l = 0; l < k; l++){
        res += gcd(i + 1, j + 1, l + 1);
      }
    }
  }

  cout << res << endl;
  
  

  return 0;
}


Measured memory_bytes: 3632
S, T = input(), input()
q = int(input())

ls, lt = len(S), len(T)
acs, act = [0]*(ls+1), [0]*(lt+1)

for i in range(1, ls+1):
    acs[i] = acs[i-1] + (S[i-1]=="A")
for i in range(1, lt+1):
    act[i] = act[i-1] + (T[i-1]=="A")

for _ in range(q):
    a, b, c, d = map(int, input().split())
    print("YES" if (acs[b]-acs[a-1]+b-a+1)%3==(act[d]-act[c-1]+d-c+1)%3 else "NO")


Measured memory_bytes: 55000
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int N, L[100];
    cin >> N;
    REP(i, N) cin >> L[i];
    sort(L, L + N);
    int ans = 0;
    REP(i, N - 2) FOR(j, i + 1, N - 1) FOR(k, j + 1, N) {
        if (L[i] + L[j] > L[k] &&
            L[i] != L[j] &&
            L[j] != L[k]
        ) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3648
#include <stdio.h>
#include<string.h>
int main(void){
    unsigned long long  n,m;
    scanf("%llu%llu",&n,&m);
    if(2*n>=m)printf("%lld\n",m/2);
    else if((m-2*n)<3)printf("%lld\n",n);
    else printf("%lld\n",n+(m-2*n)/4);
    return 0;
}


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

int main() {
  int n;
  int sum = 0;
  vector<int> vec(105);
  
  cin >> n;
  rep(i, n)
    cin >> vec.at(i);
  
  sort(vec.begin(), vec.end());
  
  for(int i = 0; i < vec.size(); i++){
    if(vec.at(i) == 0){
      continue;
    }
    
    if(vec.at(i - 1) != vec.at(i)){
      sum++;
    }
  }
  
  cout << sum << endl;

}


Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
int a[100][100],ans;
int main()
{
  int n,d;
  cin>>n>>d;
  for(int i=1;i<=n;i++) for(int j=1;j<=d;j++) cin>>a[i][j];
  for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
  {
    double temp=0;
    for(int k=1;k<=d;k++) temp+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
    temp=sqrt(temp);
    if(floor(temp)==temp) ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
// #include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <string>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <ctime>
#include <cassert>
#include <fstream>
#include <stack>
#include <random>
#include <atcoder/twosat>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

template<typename T>
void vdeb(std::vector<T> &da) {
    for (int i = 0;i < da.size();i++) {
        if (i == da.size() - 1) std::cout << da[i];
        else std::cout << da[i] << ' ';
    }
    std::cout << '\n';
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
    for (int i = 0;i < da.size();i++) {
        std::cout << i << ' ';
        vdeb(da[i]);
    }
    std::cout << '\n';
}

using namespace std;
namespace ac = atcoder;

int main() {
    ll n,d; cin >> n >> d;
    vector<Pll> da(n);
    rip(i,n,0) cin >> da[i].first >> da[i].second;
    ac::two_sat g(n);
    rip(i,n,0) {
        rip(j,i,0) {
            if(abs(da[i].first-da[j].first) < d) g.add_clause(i,false,j,false);
            if(abs(da[i].first-da[j].second) < d) g.add_clause(i,false,j,true);
            if(abs(da[i].second-da[j].first) < d) g.add_clause(i,true,j,false);
            if(abs(da[i].second-da[j].second) < d) g.add_clause(i,true,j,true);
        }
    }
    if(g.satisfiable()) {
        printf("Yes\n");
        auto ans = g.answer();
        rip(i,n,0) {
            if(ans[i]) printf("%lld\n", da[i].first);
            else printf("%lld\n", da[i].second);
        }
    }
    else {
        printf("No\n");
    }
}

Measured memory_bytes: 3744
import numpy as np
n=int(input())
H=[]
for i in range(n):
    a,b,c=map(int,input().split())
    H.append([a,b,c])

dp=[[0 for i in range(3)] for j in range(n+1)]

dp[0][0]=H[0][0]
dp[0][1]=H[0][1]
dp[0][2]=H[0][2]

for i in range(0,n-1):
    dp[i+1][0]=max(dp[i][1],dp[i][2])+H[i+1][0]
    dp[i+1][1]=max(dp[i][0],dp[i][2])+H[i+1][1]
    dp[i+1][2]=max(dp[i][0],dp[i][1])+H[i+1][2]

print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

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

//素集合データ構造
//ref:https://ei1333.github.io/luzhiled/snippets/structure/union-find.html
struct union_find {
	//parent[v]==w(>=0):vの親はw
	//parent[v]==k(<0):vは根&&vの属するグループの要素数は-k
	vector<long long int> parent;
	//コンストラクタ
	union_find(long long int n){
		parent.assign(n,-1);
	}
	//根を求める
	//求めると同時に親を根に置き換える(木の圧縮)
	long long int root(long long int v){
		if (parent[v]<0) {
			return v;
		}else {
			parent[v]=root(parent[v]);
			return parent[v];
		}
	}
	//属するグループの要素数を求める
	long long int size(long long int v){
		return -parent[root(v)];
	}
	//vとwを繋げる
	void unite(long long int v,long long int w){
		v=root(v);
		w=root(w);
		if(v==w) return;
		if (parent[v]<parent[w]) swap(v,w);
		parent[w]+=parent[v];
		parent[v]=w;
	}
	//vとwが同値か判定
	bool isSame(long long int v,long long int w){
		return root(v)==root(w);
	}
};

int main(){
	int n,m;
	cin>>n>>m;
	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		cin>>p[i];
		p[i]--;
	}
	vector<int> x(m),y(m);
	for (int i = 0; i < m; i++) {
		cin>>x[i]>>y[i];
		x[i]--;
		y[i]--;
	}
	union_find uf(n);
	for (int i = 0; i < m; i++) {
		uf.unite(x[i],y[i]);
	}
	int ans=0;
	for (int i = 0; i < n; i++) {
		if (uf.isSame(i,p[i])) {
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2176
fun main(args:Array<String>) {
    val n = readLine()!!.toInt()
    var ans = 0
    for (a in 1..n) {
        for (b in a..n) {
            for (c in b..n) {
                ans += if (a == b && b == c) {
                    gcd3(a,b,c)
                } else if (a==b || b ==c) {
                    gcd3(a,b,c)*3
                } else {
                    gcd3(a,b,c)*6
                }
            }
        }
    }
    println(ans)
}
fun gcd(a:Int,b:Int):Int {
    if (b == 0) {
        return a
    }
    return gcd(b,a%b)
}
fun gcd3(a: Int,b: Int,c:Int):Int {
    return gcd(gcd(a,b),c)
}

Measured memory_bytes: 34980
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int V;
vector<int> G[1010];
int match[1010];
bool used[1010];

void add_edge(int u, int v) {
	G[u].push_back(v);
	G[v].push_back(u);
}

bool dfs(int v) {
	used[v] = true;
	for (int i = 0; i < G[v].size(); i++) {
		int u = G[v][i];
		int w = match[u];
		if (w < 0 || !used[w] && dfs(w)) {
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}

int bipartite_matching() {
	int res = 0;
	memset(match, -1, sizeof(match));
	for (int v = 0; v < V; v++) {
		if (match[v] < 0) {
			memset(used, 0, sizeof(used));
			if (dfs(v)) {
				res++;
			}
		}
	}
	return res;
}

long long int gcd(long long int a, long long int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a%b);
	}
}

int main() {
	int m, n;
	while (cin >> m >> n) {
		if (m == 0 && n == 0) {
			break;
		}
		for (int i = 0; i < 1010; i++) {
			G[i].clear();
		}
		V = m + n;
		vector<long long int> b(m);
		vector<long long int> r(n);
		for (int i = 0; i < m; i++) {
			cin >> b[i];
		}
		for (int i = 0; i < n; i++) {
			cin >> r[i];
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (gcd(b[i], r[j]) != 1) {
					add_edge(i, m+j);
				}
			}
		}
		cout << bipartite_matching() << endl;
	}
	return 0;
}

Measured memory_bytes: 4856
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = []
for i in range(n):
    a.append(inn())
a.sort()
if n%2==0:
    m = n//2
    sa = sum(a[:m])
    sb = sum(a[m:])
    print(2*sb-2*sa-a[m]+a[m-1])
else:
    m = n//2
    sa = sum(a[:m])
    sb = sum(a[m+1:])
    if a[m+1]-a[m]>a[m]-a[m-1]:
        print(2*sb-2*sa-a[m]+a[m-1])
    else:
        print(2*sb-2*sa-a[m+1]+a[m])


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

int main()
{
    int n;
    int a1;

    cin >> n; 
    vector<vector<int>> a;
    rep(i, n) {
        vector<int> tmp;
        cin >> a1;
        tmp.push_back(a1);
        tmp.push_back(i+1);
        a.push_back(tmp);
    }

    sort(a.begin(), a.end(), [](const vector<int>& alpha, const vector<int>& beta) {return alpha[0] < beta[0];});

    rep(i,n-1)
        std::cout << a[i][1] << " ";
    std::cout << a[n-1][1] << endl;

    return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  map<int, int> data;
  
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;
    
    data[A] += 1;
  }
  
  bool dif = true;
  
  for (auto d : data) {
    if (d.second != 1) {
      dif = false;
      break;
    }
  }
  
  if (dif) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 9600
#include<stdio.h>
#include<algorithm>
using namespace std;
int digit[]={119,36,93,109,46,107,123,37,127,111};
int L[120];
int R[120];
int mask[20];
int month[]={31,28,31,30,31,30,31,31,30,31,30,31};
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<20;i++)mask[i]=127;
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		mask[13-p]-=(1<<q);
	}
	for(int i=0;i<10000;i++){
		for(int j=1;j<=12;j++){
			if(j==2&&(i%400==0||(i%100!=0&&i%4==0))){
				month[j-1]++;
			}
			for(int k=1;k<=month[j-1];k++){
				int num=i*10000+j*100+k;
				int cnt=0;
				for(int l=6;l<=13;l++){
					cnt+=__builtin_popcount(digit[num%10]&mask[l]);
					num/=10;
				}
				L[cnt]++;
			}
			if(j==2&&(i%400==0||(i%100!=0&&i%4==0))){
				month[j-1]--;
			}
		}
	}
	for(int i=0;i<24;i++){
		for(int j=0;j<60;j++)for(int k=0;k<60;k++){
			int num=i*10000+j*100+k;
			int cnt=0;
			for(int l=0;l<=5;l++){
				cnt+=__builtin_popcount(digit[num%10]&mask[l]);
				num/=10;
			}
			R[cnt]++;
		}
	}
	long long ret=0;
	for(int i=0;i<=a;i++){
		ret+=(long long)L[i]*R[a-i];
	}
	printf("%lld\n",ret);
}

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

typedef long long ll;

//入力
int N,W;
vector<ll> w(105);
vector<ll> v(105);

//DP table
ll dp[105][100005];

int main() {
	cin>>N>>W;
	rep(i,N){
		cin>>w[i]>>v[i];
	}
	rep(i,N)rep(j,W+1){
		//i番目の品物を選ぶとき
		//i + 1行目で、j+w[i]がWを超えないような範囲でdp table を更新していく
		//具体的には、
		if(j+w[i]<=W){
			dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
		}
		//i番目の品物を選ばないとき
		//dp table の価値は変わらず、そのまま下に降りる
		dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
	}
	cout<<dp[N][W]<<endl;
}

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

int main()
{
    int i,a,b,s1,s2;
    s1=s2=0;
    scanf("%d %d",&a,&b);
    for(i = 0;i < a;i++)
        s1 = s1*10+b;
    for(i = 0;i < b;i++)
        s2 = s2*10+a;
    if(s1 > s2)
        printf("%d",s1);
    else
        printf("%d",s2);
    return 0;
}

Measured memory_bytes: 128
def pd(n,p):
    if n%p==0:
        return pd(n/p,p)+1
    else:
        return 0


Plist=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
N=int(raw_input())
if N==1:
    print 1
else:
    A=[1 for i in Plist]
    for n in range(1,N+1):
        for p in range(len(Plist)):
            A[p]+=pd(n,Plist[p])
    B=1000000007
    ans=1
    for a in A:
        ans*=a
        ans%=B
    print ans

Measured memory_bytes: 2820
#include <algorithm>
#include <iostream>

using namespace std;

constexpr static int MAXN = 1e6;
int deg[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        deg[a]++, deg[b]++;
    }
    for (int i = 0; i < n; i++)
        if (deg[i] % 2 == 1) {
            cout << "NO" << endl;
            return 0;
        }
    cout << "YES" << endl;
}


Measured memory_bytes: 640
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)

	for i := 0; i < len(s); i++ {
		if i == len(s) - 1 {
			fmt.Println("x")
		} else {
			fmt.Print("x")
		}
	}
}


Measured memory_bytes: 512
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=1000023;
bool vis[N];
vector <int> adj[N];
ll fact[N];
ll invfact[N];
ll inv[N];
void factorialsComputation()
{
    inv[0]=inv[1]=1;
    fact[0]=fact[1]=1;
    invfact[0]=invfact[1]=1;
    for(int i=2;i<N;i++)
    {
        inv[i]=(inv[mod%i]*(mod-mod/i))%mod;
        fact[i]=(fact[i-1]*i)%mod;
        invfact[i]=(invfact[i-1]*inv[i])%mod;
    }
}
ll ncr(ll n,ll r)
{
    ll ans=fact[n];
    ans*=(invfact[r]);
    ans%=mod;
    ans*=(invfact[n-r]);
    ans%=mod;
    return ans;
}
void solve()
{
    ll n;
    cin>>n;
    ll f[n+1]={0};
    int low=(n+1)/2;
    for(int k=low;k<=n-1;k++)
    {
        f[k]=(ncr(k-1,n-k-1))*fact[k];
        f[k]%=mod;
        f[k]*=fact[n-1-k];
        f[k]%=mod;
    }
    ll ans=0;
    for(int k=low;k<=n-1;k++)
    {
        ll ways=f[k]-f[k-1]+mod;
        ways%=mod;
        ways*=k;
        ways%=mod;
        ans+=ways;
        ans%=mod;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    //cin>>T;
    int t=0;
    factorialsComputation();
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 55168
#include<iostream>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
int main()
{
	int n, x[100];
	int i, j, k;
	unsigned long tmp, ans;

	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> x[i];
	}

	sort(x, x + n);

	ans = LONG_MAX;
	for (i = 1; i <= x[n-1]; i++) {
		tmp = 0;
		for (j = 0; j < n; j++) {
			tmp += (i - x[j])*(i - x[j]);
		}
		ans = min(tmp, ans);
	}
	cout << ans << endl;
}



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

int main() {
  int A,B;
  cin >> A >> B;
  
  if(A==B)
    cout << "Draw" << endl;
  else if(A == 1)
    cout << "Alice" << endl;
  else if(B == 1)
    cout << "Bob" << endl;
  else if(A<B)
    cout << "Bob" << endl;
  else 
    cout << "Alice" << endl;    
  }

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
#define md 998244353
#define INF LLONG_MAX
#define F first
#define S second
#define sz(x) (long long)x.size()
#define vi vector<int>
#define vll vector<long long>
#define vpl vector<pair<long long,long long> >
#define vpi vector<pair<int,int> >
#define pb push_back
#define debug(x) cerr<<#x<<"= "<<x<<endl
#define all(v) v.begin(),v.end()
#define TT ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define endl '\n'
#define MAXN 200005
typedef long long ll;
typedef long double ld;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll n,m;
    cin>>n>>m;
    ll ans=(n)*(n-1)/2;
    ans+=m*(m-1)/2;
    cout<<ans;


    return 0;
}

Measured memory_bytes: 256
url = "https://atcoder.jp//contests/abc110/tasks/abc110_b"

def main():
    n, m, x, y = list(map(int, input().split()))
    xs = list(map(int, input().split()))
    ys = list(map(int, input().split()))
    xs.sort()
    ys.sort()
    if xs[-1] >= ys[0]:
        print('War')
        exit()
    for i in range(xs[-1] + 1, ys[0] + 1):
        if x < i <= y:
            print('No War')
            exit()
    print('War')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9188
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math

A,B,C,D,E,F = map(int,input().split())

water = []
for ai in range(int(F/(A*100))+1):
    for bi in range(int(F/(B*100))+1):
        if (ai*A+bi*B)*100>F:pass
        else:
            water.append((ai*A+bi*B)*100)

suger = []
for ci in range(int(F/C)+1):
    for di in range(int(F/D)+1):
        if ci*C+di*D > F:
            pass
        else:suger.append(ci*C+di*D)

water = list(set(water))
suger = list(set(suger))
water.remove(0)
pure = 0
ans_s,ans_w = 0,A*100
for wi in range(len(water)):
    for si in range(len(suger)):
        if water[wi]+suger[si]>F:pass
        else:
            if pure<suger[si]/(water[wi]+suger[si])<=(E/(100+E)):
                ans_s = suger[si]
                ans_w = water[wi]
                pure = suger[si]/(water[wi]+suger[si])

print(ans_s+ans_w,end="")
print(" ",end="")
print(ans_s)


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

int main() {
    int N,Y;
    cin >> N >> Y;
    int sum = 0;
    int a,b,c;
    a = b = c = -1;
    for (int i = 0; i <= N; i++){
        for (int j = 0; j <= N; j++){
            if ((0 <= (N - i - j)) && ((N - i - j) <= N)){
                sum = 10000 * i + 5000 * j + 1000 * (N - i - j);
                if (sum == Y){
                    a = i;
                    b = j;
                    c = N - i - j;
                }
            }
        }
    }
    cout << a << " " << b << " " << c << endl;
}

Measured memory_bytes: 3596
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

#define MAX_WLEN	(20)

/* typedef */

typedef vector<int> vi;
typedef vector<string> vs;

class LessWord {
public:
  bool operator()(const string& w0, const string& w1) const {
    return w1.size() < w0.size() || (w1.size() == w0.size() && w0 < w1);
  }
};

/* global variables */

int nus;
int tbl[26];
string ptxt;
vs seq, useq, words[MAX_WLEN + 1];

/* subroutines */

string dcword(string& w) {
  //cout << "dcword:" << w << endl;
  string dcw = string();

  for (int i = 0; i < w.size(); i++)
    dcw += tbl[w[i] - 'A'] + 'A';

  return dcw;
}

void decipher(int k) {
  //cout << "decipher:" << k << endl;
  if (k >= nus) {
    if (ptxt == "") {
      for (int i = 0; i < seq.size(); i++) {
	if (i > 0) ptxt += ' ';
	ptxt += dcword(seq[i]);
      }
      return;
    }
    ptxt = "-";
    return;
  }

  string& usw = useq[k];
  int uslen = usw.size();
  vi rpl;

  for (int i = 0; i < words[uslen].size(); i++) {
    string& word = words[uslen][i];
    int ok = 1;
    rpl.clear();
    
    for (int j = 0; j < uslen; j++) {
      int uswj = usw[j] - 'A';
      int wj = word[j] - 'A';
      if (tbl[uswj] < 0 && tbl[wj] < 0) {
        rpl.push_back(uswj);
        rpl.push_back(wj);
        tbl[uswj] = wj;
	tbl[wj] = uswj;
      }
      else if (tbl[uswj] != wj) {
        ok = 0;
        break;
      }
    }

    if (ok) {
      decipher(k + 1);
      if (ptxt == "-") return;
    }

    for (vi::iterator vit = rpl.begin(); vit < rpl.end(); vit++)
      tbl[*vit] = -1;
  }
}

/* main */

int main() {
  int n;

  for (;;) {
    cin >> n;
    if (n == 0) break;

    for (int i = 0; i <= MAX_WLEN; i++)
      words[i].clear();
    
    for (int i = 0; i < n; i++) {
      string w = string();
      cin >> w;
      //cout << w << endl;
      words[w.size()].push_back(w);
    }
    //for (int i = 0; i <= MAX_WLEN; i++) cout << words[i].size() << endl;
    
    seq.clear();
    for (;;) {
      string w = string();
      cin >> w;
      //cout << w << endl;
      string::size_type loc = w.find('.', 0);
      if (loc != string::npos) {
	w.erase(loc);
	seq.push_back(w);
	break;
      }
      seq.push_back(w);
    }
    //for (int i = 0; i < seq.size(); i++) cout << seq[i] << endl;

    set<string> seqset = set<string>(seq.begin(), seq.end());
    useq = vs(seqset.begin(), seqset.end());
    sort(useq.begin(), useq.end(), LessWord());
    nus = useq.size();
    //for (int i = 0; i < nus; i++) cout << useq[i] << endl;
    //  #p $words
    //  #p $useq

    for (int i = 0; i < 26; i++) tbl[i] = -1;
    ptxt = "";

    decipher(0);

    cout << ptxt << '.' << endl;
  }

  return 0;
}

Measured memory_bytes: 1252
# -*- coding: utf-8 -*-
import math

class KochCurve(object):
	# public変数
	x = 0.0
	y = 0.0

	# private変数
	#__xy = 0.0

	# 解法
	def koch(self, n, a, b):
		if n == 0:
			return 

		s = KochCurve()
		t = KochCurve()
		u = KochCurve()
		th = math.pi * 60.0 / 180.0

		s.x = (2.0 * a.x + 1.0 * b.x) / 3.0
		s.y = (2.0 * a.y + 1.0 * b.y) / 3.0
		t.x = (1.0 * a.x + 2.0 * b.x) / 3.0
		t.y = (1.0 * a.y + 2.0 * b.y) / 3.0
		u.x = (t.x - s.x) * math.cos(th) - (t.y - s.y) * math.sin(th) + s.x
		u.y = (t.x - s.x) * math.sin(th) + (t.y - s.y) * math.cos(th) + s.y
		
		KochCurve().koch(n - 1, a, s)
		msg = "%.8f %.8f" % (s.x, s.y)
		print(msg)
		KochCurve().koch(n - 1, s, u)
		msg = "%.8f %.8f" % (u.x, u.y)
		print(msg)
		KochCurve().koch(n - 1, u, t)
		msg = "%.8f %.8f" % (t.x, t.y)
		print(msg)
		KochCurve().koch(n - 1, t, b)


if __name__ == '__main__':
	a = KochCurve()
	b = KochCurve()

	n = int(input())

	a.x = 0
	a.y = 0
	b.x = 100
	b.y = 0

	msg = "%.8f %.8f" % (a.x, a.y)
	print(msg)
	KochCurve().koch(n, a, b)
	msg = "%.8f %.8f" % (b.x, b.y)
	print(msg)


Measured memory_bytes: 5764
// I - Coins
// A. Bacca
#include <bits/stdc++.h>
using namespace std;

int n;
vector <long double> probs;
vector <vector <long double> > dp;

void Recibir() {
	cin >> n;
	probs.resize(n);
	for (int i=0; i<n; i++) cin >> probs[i];
	dp.resize(n);
	for (int i=0; i<n; i++) dp[i].assign(2*n+1, -1);
} 

long double Exec(int idx, int cnt) {
	// Caso base (+ = mas caras, - = menos caras)
	if (idx == n) return (cnt > 0 ? 1 : 0);
	// DP
	if (dp[idx][cnt+n] != -1) return dp[idx][cnt+n];
	// Caso recursivo
	else {
		// Caras + Colas
		return dp[idx][cnt+n] = (long double) (probs[idx]*Exec(idx+1, cnt+1) + (1.0-probs[idx])*Exec(idx+1, cnt-1));
	}
}

int main() {
	Recibir();
	cout << setprecision(10) << Exec(0, 0);
	return 0;
}

Measured memory_bytes: 281728
/* To Kaise Hain Aaplog*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) (x).begin(), (x).end()

void shuru_krte_hai_bina_kisi_bakchodi_ke()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
const ll m = 998244353;

const ll s = 1e7+2;
ll a[s];
int main()
{
    //shuru_krte_hai_bina_kisi_bakchodi_ke();

    /* long long yaad se daal de har jagah*/
    #define int long long
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j = 0;j<=n;j+=i){
            a[j]++;
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        ans+=(i*a[i]);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 81768
#include<cstdio>
#include<cstring>
#define MAXN 1000
int A,B,C,D;char s[MAXN+5];
int main()
{
	A=B=C=D=1;
	scanf("%s",s+1);
	for(int i=1;i<=strlen(s+1);i++)
	A&=(s[i]!='N'),B&=(s[i]!='S'),C&=(s[i]!='W'),D&=(s[i]!='E');
	printf("%s",(A^B)||(C^D)?"No":"Yes");
}

Measured memory_bytes: 128
#include <stdio.h>
 
int face[7][7][4] = {
{{0},{0},{0},{0},{0},{0},{0}},
{{0},{0},{0,1,2,3},{0,1,3,5},{0,1,4,2},{0,1,5,4},{0}},
{{0},{0,2,1,4},{0},{0,2,3,1},{0,2,4,6},{0},{0,2,6,3}},
{{0},{0,3,1,2},{0,3,2,6},{0},{0},{0,3,5,1},{0,3,6,5}},
{{0},{0,4,1,5},{0,4,2,1},{0},{0},{0,4,5,6},{0,4,6,2}},
{{0},{0,5,1,3},{0},{0,5,3,6},{0,5,4,1},{0},{0,5,6,4}},
{{0},{0},{0,6,2,4},{0,6,3,2},{0,6,4,5},{0,6,5,3},{0}}};
int assign[7];
 
int main()
{
    int q, i, t, f;
 
    for (i = 1; i <= 6; i++) scanf("%d", assign+i);
    scanf("%d", &q);
    while (q--) {
        scanf("%d%d", &t, &f);
        for (i = 1; i <= 6; i++) {
            if (assign[i] == t) t = i;
            if (assign[i] == f) f = i;
        }
        printf("%d\n", assign[face[t][f][3]]);
    }
    return 0;
}



Measured memory_bytes: 2076
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  int h[100005];
  int dp[100005];

  cin>>n;
  for(int i=0;i<n;i++) cin>>h[i];

  dp[0]=0; dp[1]=abs(h[0]-h[1]);

  for(int i=2;i<n;i++){
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
  }

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pa pair<int, int>
using namespace std;

int n, a[200010], f[200010][2], cnt = 0;
bool h[200010];
struct BIT
{
    vector<pa> s[200010];
    void insert(int x, int y, int pos)
    {
        for (int i = x; i <= n; i += i & -i)
        {
            if (s[i].empty() || s[i].back().second < y) s[i].emplace_back(pos, y);
        }
    }
    int get(int x, int pos)
    {
        int ans = 0xefefefef;
        for (int i = x; i > 0; i -= i & -i)
        {
            while (!s[i].empty() && s[i].back().first < pos) s[i].pop_back();
            if (!s[i].empty()) ans = max(ans, s[i].back().second);
        }
        return ans;
    }
} s[2];
char ans[200010];

bool chk(int x, int mx, int pos)
{
    if (x < 0) return false;
    if (x == 0) return true;
    if (mx == 0) mx = 1;
    int f[2] = {s[0].get(n - mx + 1, pos), s[1].get(n - mx + 1, pos)};/*
    printf("%d %d %d %d\n", pos, f[0], f[1], mx);
    for (int i = 1; i <= n; i++)
    {
        for (pa x : s[1].s[i])
            printf("(%d, %d)", x.first, x.second);
        puts("");
    }*/
    if (x & 1)
    {
        return f[1] >= x;
    }
    else
    {
        return f[1] >= x || f[0] >= x;
    }
}
int main()
{
    scanf("%d", &n);
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] > mx)
        {
            h[i] = true;
            mx = a[i];
            cnt++;
        }
    }
    for (int i = n; i > 0; i--)
    {
        if (h[i])
        {
            f[i][0] = max(2, s[0].get(n - a[i] + 1, i) + 2);
            f[i][1] = s[1].get(n - a[i] + 1, i) + 2;
            s[0].insert(n - a[i] + 1, f[i][0], i);
            s[1].insert(n - a[i] + 1, f[i][1], i);
        }
        else
        {
            f[i][1] = max(1, max(s[0].get(n - a[i] + 1, i), s[1].get(n - a[i] + 1, i)) + 1);
            s[1].insert(n - a[i] + 1, f[i][1], i);
        }
    }
    for (int i = n - 1; i > 0; i--)
    {
        f[i][0] = max(f[i][0], f[i + 1][0]);
        f[i][1] = max(f[i][1], f[i + 1][1]);
    }/*
    for (int i = 1; i <= n; i++)
    {
        printf("%d %d\n", f[i][0], f[i][1]);
    }
    puts("");*/
    if (!chk(cnt, 1, 1))
    {
        puts("-1");
        return 0;
    }
    int c = 0, mx1 = 0, mx2 = 0;
    for (int i = 1; i <= n; i++)
    {
        if (h[i]) cnt--;
        if (a[i] > mx1) c++;
        int hh1 = cnt + c, hh2 = cnt - c;
        // printf("%d %d %d %d %d %d %d\n", i, cnt, c, hh1, hh2, mx1, mx2);
        if (chk(hh1, mx2, i + 1) || chk(hh2, max(mx1, a[i]), i + 1))
        {
            mx1 = max(mx1, a[i]);
            ans[i] = '0';
        }
        else
        {
            if (a[i] > mx1) c--;
            if (a[i] > mx2) c--, mx2 = a[i];
            ans[i] = '1';
        }
    }
    puts(ans + 1);
}

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

int N;

vector<pair<int, int>> red(101);
vector<pair<int, int>> blue(101);

bool cmp(const pair<int, int>& a, const pair<int, int>& b){
    return a.second > b.second;
}

int main(void){
    
    cin >> N;
    for(int i = 0; i < N; ++i) cin >> red[i].first >> red[i].second;
    for(int i = 0; i < N; ++i) cin >> blue[i].first >> blue[i].second;
    
    sort(red.begin(), red.begin() + N, cmp);
    sort(blue.begin(), blue.begin() + N);
    
    
    bitset<101> bit;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(!bit[j] && blue[i].first > red[j].first && blue[i].second > red[j].second){
                bit.set(j);
                break;
            }
        }
    }
    cout << bit.count() << endl;
    
    return 0;
}

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



signed main()
{
    int x;
	cin>>x;
	int val[6]={100,101,102,103,104,105};
	
    vector<bool> dp(x+1,false);
    dp[0]= true;
    for(int i=0;i<6;i++){
        for(int j=1;j<=x;j++){
            if(j>=val[i]) dp[j]= dp[j] || dp[j-val[i]];
        }
    }
    
    if(dp[x]) cout<<"1";
    else cout<<"0";
    
	return 0;
}


Measured memory_bytes: 256
object Main extends App {
  import scala.io.StdIn._

  val n  = readInt()
  val an = readLine().split(" ").map(_.toInt)

  val ans = an.foldLeft((0L, 0)) { case ((total, height), a) =>
    (total + 0.max(height - a), a max height)
  }._1

  println(ans)
}


Measured memory_bytes: 86268
#include <bits/stdc++.h>
#define eps 1e-3
#define pi acos(-1.0)
#define inf 0x3f
#define INF 0x3f3f3f3f
#define pb push_back
#define debug1 cout<<"&&";
#define debug2 cout<<"**";
#define ms(a, x) memset(a, x, sizeof(a))
#define for0(i, n) for(int i = 0; i < n; ++i)
#define for1(i, n) for(int i = 1; i <= n; ++i)
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
const int mod = 1e9 + 7;
const int N = 1e5+10;
const int M = 1e6+10;
/*=================================================================================*/

int n, tot, head[N], ver[N<<2], nex[N<<2];
ll dp[N][2];

void add(int x, int y) {
   ver[++tot] = y;
   nex[tot] = head[x];
   head[x] = tot;
}

void dfs(int x, int fa) {
   ll a = 1, b = 1;
   if(nex[head[x]] == 0 && ver[head[x]] == fa) {
      dp[x][0] = dp[x][1] = 1;
      return;
   }
   for(int i = head[x]; i; i = nex[i]) {
      int y = ver[i];
      if(y == fa) continue;
      dfs(y, x);
      a = (a * ((dp[y][0] + dp[y][1]) % mod)) % mod;
      b = (b * dp[y][0]) % mod;
   }
   dp[x][0] = a, dp[x][1] = b;
}

int main() {
   cin>>n;
   for0(i, n-1) {
      int x, y;
      scanf("%d %d", &x, &y);
      add(x, y), add(y, x);
   }
   dfs(1, 0);
   cout << (dp[1][0] + dp[1][1]) % mod << endl;
   return 0;
}

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

int main() {
	int d, g;
	cin >> d >> g;
	int p[10], c[10];
	for (int i = 0; i < d; i++) {
		cin >> p[i] >> c[i];
	}
	int num;
	int point, ans, answer = 1e9;
	int r;
	for (int i = 0; i <= pow(2, d); i++) {
		num = i;
		point = 0;
		ans = 0;
		for (int j = 0; j < d; j++) {
			if (num % 2 == 1) {
				point += 100 * (j + 1)*p[j] + c[j];
				ans += p[j];
			}
			else {
				r = j;
			}
			num /= 2;
		}
		if (point < g) {
			int s = 100 * (r + 1);
			int need= (g - point + s - 1) / s;
			if (need >= p[r]) {
				continue;
			}
			ans += need;
		}
		answer = min(ans, answer);
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int a,b,c,k,n,cnt;
string s,t;
signed main()
{
	cin>>n>>s;
	rep(i,n-2){
		if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C'){
			cnt++;
		}
	}
	cout<<cnt;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    KS = [il() for _ in range(M)]
    P = il()

    ret = 0
    for n in range(1 << N):
        l = [False]*M
        for m in range(len(KS)):
            K, *S = KS[m]
            on = 0
            for s in S:
                if n >> (s-1) & 1:
                    on += 1
            if on % 2 == P[m]:
                l[m] = True
        if all(l):
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()


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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());


void c_p_c()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
 // c_p_c();
  string a,b;
  cin >> a;
  cin >> b;
  if(a.size() != b.size())
  {
    cout<<"No"<<endl;
  }
  else
  {
      set <char> s1,s2;
      int pos = -1;
    for(int i=0;i<a.size();i++)
    {
      s1.insert(a[i]);
    }
    int t = 0;
    for(int i=0;i<b.size();i++)
    {
      if(b[i] == a[0] && t == 0)
      {
        pos = i;
        t = 1;
      }
      s2.insert(b[i]);
    }
    if(s1 != s2)
    {
      cout<<"No"<<endl;
    }  
    else
    {
      bool ans = false;
      string ts = a + a;
      for(int i = 0;i<ts.size();i++)
      {
        string req = ts.substr(i,a.size());
        if(req == b)
        {
          ans = true;
          break;
        }
      }
      if(ans)
      {
        cout<<"Yes"<<endl;
      }
      else
      {
        cout<<"No"<<endl;
      }
    }
  }
  
  return 0;
}



Measured memory_bytes: 256
from collections import Counter
N = int(input())
s= input()

D = Counter(s[1:])["E"]
nums = [D]
for i in range (1,N):
    temp = nums[-1]
    if s[i-1] == "W":
        temp += 1
    if s[i] == "E":
        temp -= 1
    nums.append(temp)

print(min(nums))

Measured memory_bytes: 15812
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  string s;
  cin>>n>>s;
  
  ll r=0,g=0,b=0;
  rep(i,n){
    if(s[i]=='R') r++;
    else if(s[i]=='G') g++;
    else if(s[i]=='B') b++;
  }
  
  ll ans = r*g*b;

  for(int i=1;i<=(n-1)/2;i++){
    for(int j=0;j<(n-2*i);j++){
      if(s[j]=='R' && s[j+i]=='G' && s[j+2*i]=='B') ans--;
      if(s[j]=='R' && s[j+i]=='B' && s[j+2*i]=='G') ans--;
      if(s[j]=='G' && s[j+i]=='R' && s[j+2*i]=='B') ans--;
      if(s[j]=='G' && s[j+i]=='B' && s[j+2*i]=='R') ans--;
      if(s[j]=='B' && s[j+i]=='R' && s[j+2*i]=='G') ans--;
      if(s[j]=='B' && s[j+i]=='G' && s[j+2*i]=='R') ans--;
    }
  }   
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3600
// C - To Infinity
// https://abc106.contest.atcoder.jp/tasks/abc106_c

import scala.io.StdIn.readLine

object Main extends App {

  val s = readLine.toCharArray
  val k = BigInt(readLine)

  def solve(k: BigInt, i: Int = 0): Char = {
    if (s(i) != '1' || k == 1) s(i)
    else solve(k-1, i+1)
  }

  val num = solve(k)

  println(num)

}

Measured memory_bytes: 27068