akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end());

    long long M = a[n - 1];
    long long d[1000000 + 10] = {0};

    for(int i = 0;i < n;i++){
        for(int j = 1;j*a[i] <= M;j++){
            d[a[i]*j]++;
        }
    }

    /*
    for(int i = 1;i <= M;i++){
        cout << d[i] << " ";
    }

    cout << endl;
    */

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

    cout << ans << endl;

    
}


Measured memory_bytes: 12704
#line 1 "/workspaces/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; }

void say(bool val, string yes = "Yes", string no = "No") { say<string>(val, yes, no); }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}

// C++ 17に完全移行したら消す
// 最大公約数を求める
template <class T> T gcd(T n, T m) { return n ? gcd(m % n, n) : m; }

// 最小公倍数を求める
template <class T> T lcm(T n, T m) {
  int g = gcd(n, m);
  return n * m / g;
}

// 重複を消す。計算量はO(NlogN)
template <class T> void unique(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
}


#line 2 "abc172_d.cpp"

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

  int n;
  cin >> n;

  vl cum(n + 1);
  cum[0] = 0;
  FOR(i, 1, n + 1) { cum[i] = cum[i - 1] + (ll)i; }

  ll ans = 0;
  FOR(i, 1, n + 1) { ans += cum[n / i] * (ll)i; }
  cout << ans << endl;
}


Measured memory_bytes: 81312
#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <map>
using namespace std;
typedef pair<int,int> P;
map<P,int> M;

int main(){
    int N;
    cin>>N;
    int ans=0;
    for(int i=0;i<N;i++){
        int j;
        cin>>j;
        j--;
        if(M.find(P(min(i,j),max(i,j)))!=M.end()){
            ans++;M[P(min(i,j),max(i,j))]++;
        }else{
            M[P(min(i,j),max(i,j))]=1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6528
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

const int INF = 1e9;
const int MOD = 1000000007;

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

  if (S == "ABC") {
    cout << "ARC" << endl;
  } else {
    cout << "ABC" << endl;
  }

  return 0;
}


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


int main() {
  ios::sync_with_stdio(false);
	cin.tie(0);
  int n,m;
  cin>>n>>m;
  vector<int> v(n,-1);
  rep(i,m){
    int s,c;
    cin>>s>>c;
    s--;
    if (v[s]==-1) v[s]=c;
    else{
      if (v[s]==c)continue;
      else {
        cout<<-1;
        return 0;
      }
    }
  }
rep(i,n){
  if (n>=2 and i==0){
    if (v[i]==0)
    {
    cout<<-1;
    return 0;
  }
  }
  if (v[i]==-1) {
    if (i==0 and n>=2) v[i]=1;
    else v[i]=0;
  }
  cout<<v[i];
}
}


Measured memory_bytes: 256
N, K = map(int, input().split())
if K % 2 == 0:
    # Kで割った時の余りが0のもの
    ans = (N // K) ** 3
    # Kで割った時の余りがK/2のもの
    ans += ((N + K // 2) // K) ** 3
else:
    ans = (N // K) ** 3

print(ans)


Measured memory_bytes: 38384
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int x = Integer.parseInt(sc.next());
        int t = Integer.parseInt(sc.next());
        sc.close();

        // 主処理
        int result = Math.max(0, x - t);

        // 出力
        System.out.println(result);
    }
}


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

#define all(s) s.begin(), s.end()
#define vi vector<int>
#define pb push_back
#define ii pair<int, int>
#define x first
#define y second

int b[105];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    vi ans;
    while (n != 0) {
        int foo = 0;
        for (int i = n; i >= 1; i--) {
            if (b[i] == i) {
                foo = i;
                break;
            }
        }
        //cout << foo << endl;
        if (foo == 0) return cout << - 1, 0;
        ans.pb(foo);
        for (int i = foo; i <= n - 1; i++) {
            b[i] = b[i + 1];
        }
        n--;
    }
    reverse(all(ans));
    for (int u : ans) cout << u << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <random>
#include <algorithm>
#include <functional>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N,M;
  cin>>N>>M;
  priority_queue<int> q;
  REP(i,N){
    int tmp;
    cin>>tmp;
    q.push(tmp);
  }
  REP(i,M){
    int ma=q.top();
    q.pop();
    q.push(ma/2);
  }
  ll ans=0ll;
  while(!q.empty()){
    int tmp=q.top();
    ans+=tmp;
    q.pop();
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=998244353;
const LL LINF=1LL<<62;
const int INF=1<<20;


string s[12];
int h,w;
bool used[12];
int order[12];

bool check(){
    bool cc[12];
    memset(cc,false,sizeof(cc));
    string t[h];
    for (int i = 0; i < h; i++) {
        if(i%2) t[i/2]=s[order[i]];
        else t[h-i/2-1]=s[order[i]];
    }
    for (int i = 0; i < w; i++) {
        if(cc[i]) continue;
        string a="";
        for (int j = 0; j < h; j++) {
            a.pb(t[j][i]);
        }
        for (int j = i+1; j < w; j++) {
            if(cc[j]) continue;
            string b="";
            for (int k = 0; k < h; k++) {
                b.pb(t[k][j]);
            }
            reverse(ALL(b));
            if(a==b){
                cc[i]=true;
                cc[j]=true;
                break;
            }
        }
    }
    int cnt=0;
    for (int i = 0; i < w; i++) {
        cnt+=(!cc[i]);
    }
    return cnt<=1;
}

bool dfs(int m,int k){
    if(m==h){
        return check();
    }
    if(m==h-1){
        for (int i = 0; i < h; i++) {
            if(used[i]) continue;
            used[i]=1;
            order[m]=i;
            if(dfs(m+1,k)) return true;
            used[i]=0;
        }
        return false;
    }
    for (int i = k+1; i < h; i++) {
        if(used[i]) continue;
        used[i]=1;
        order[m]=i;
        if(m%2){
            if(dfs(m+1,k)) return true;
        }
        else{
            if(dfs(m+1,i)) return true;
        }
        used[i]=0;
    }
    return false;
}

int main(){
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }
    if(dfs(0,-1)) puts("YES");
    else puts("NO");
    return 0;
}



Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
ans = 0
cnt = 0
mini = float("inf")
for i in range(N):
    ans += abs(A[i])
    mini = min(mini, abs(A[i]))
    if A[i] < 0:
        cnt += 1
        
if cnt % 2:
    ans -= 2 * mini
print(ans)

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

const double PI = 3.14159265358979323846;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//typedef pair<ll, ll> P;
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
//const ll mod = 1e10;
typedef priority_queue<string, vector<string>, greater<string> > PQ_ASK;


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

    auto ma_it = max_element(numbers.begin(), numbers.end());
    ll ma = *ma_it;
    int ma_i = distance(numbers.begin(), ma_it);
    auto mi_it = min_element(numbers.begin(), numbers.end());
    ll mi = *mi_it;
    int mi_i = distance(numbers.begin(), mi_it);

    vector<P> ans;

    if (ma + mi >= 0) {
        rep(i, n) {
            if (numbers[i] < 0) ans.push_back(P(ma_i, i));
        }
        for (int i = 1; i < n; i++) {
            ans.push_back(P(i - 1, i));
        }
    } else {
        rep(i, n) {
            if (numbers[i] > 0) ans.push_back(P(mi_i, i));
        }
        for (int i = n - 2; i >= 0; i--) {
            ans.push_back(P(i + 1, i));
        }
    }


    cout << ans.size() << endl;
    for (P p : ans) {
        printf("%lld %lld\n", p.first + 1, p.second + 1);
    }

}



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

int main() {
  string s;
  cin>>s;
  int n=s.size();
  ll dp0[n+1];
  ll dp1[n+1];
  dp0[0]=0;
  dp1[0]=1;
  rep(i,0,n){
    if(s[i]=='0'){
      dp0[i+1]=dp0[i]*3%mod;
      dp1[i+1]=dp1[i]%mod;
    }
    else{
      dp0[i+1]=(dp0[i]*3%mod+dp1[i])%mod;
      dp1[i+1]=dp1[i]*2%mod;
    }
  }
  cout<<(dp0[n]+dp1[n])%mod<<endl;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define Finline __inline__ __attribute__ ((always_inline))
#define DEBUG printf("Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define trav(a, x) for (auto& a : x)
using namespace std;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define resz resize

#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define sort_by(x, y) sort(all(x), [&](const auto& a, const auto& b) { return y; })

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;

using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;

const int inf=0x3f3f3f3f,Inf=0x7fffffff;
const ll INF=0x7fffffffffffffff;
const double eps=1e-8;

uint seed=19260817;
const uint _RAND_MAX_=4294967295u;
Finline uint Rand(){return seed=seed*998244353u+1000000007u;}

template <typename T>T gcd(const T &a,const T &b){return (!b)?a:gcd(b,a%b);}
template <typename T>Finline T abs(const T &a){return a>0?a:-a;}
template <typename T>Finline T mmax(const T &a,const T &b){return a<b?b:a;}
template <typename T>Finline T mmin(const T &a,const T &b){return a<b?a:b;}
template <typename T>Finline void chmax(T &a,const T &b){(a<b)&&(a=b);}
template <typename T>Finline void chmin(T &a,const T &b){(a>b)&&(a=b);}
template <typename T>Finline bool _cmp(const T &a,const T &b){return abs(a-b)<=eps;}
template <typename T>Finline void read(T& x)
{
    register char ch(getchar());
    bool f(false);
    while(ch<48||ch>57) f|=ch==45,ch=getchar();
    x=ch&15,ch=getchar();
    while(ch>=48&&ch<=57) x=(((x<<2)+x)<<1)+(ch&15),ch=getchar();
    if(f) x=-x;
}
template <typename T,typename... Args>Finline void read(T &t,Args &...args)
{
    read(t);read(args...);
}
Finline int read_str(char *s)
{
    register char ch(getchar());
    while(ch==' '||ch=='\r'||ch=='\n') ch=getchar();
    register char *tar=s;
    *tar=ch,ch=getchar();
    while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!=EOF) *(++tar)=ch,ch=getchar();
    return tar-s+1;
}



void solve(){
    int n;
    read(n);
    string s;
    cin >> s;
    if(n&1){
        printf("No\n");
        return;
    }
    int t=n/2;
    rep(i,0,t){
        if(s[i]!=s[i+t]){
            printf("No\n");
            return;
        }
    }
    printf("Yes\n");
}

int main(int argc, char **argv)
{
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}
// LONG LONG 9223372036854775807 , over 9*10^18
// LONG,INT 2147483647, over 2*10^9
// SHORT INT 32767, over 3*10^4
// CHAR 127, over 1*10^2



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define INF (1<<29)
using namespace std;
typedef long long ll;
int main(){
      int a[3],b[2];
      REP(i,3)cin>>a[i];
      REP(i,2)cin>>b[i];
      sort(a,a+3);
      sort(b,b+2);
      cout<<a[0]+b[0]-50<<endl;
}

Measured memory_bytes: 1176
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String O = sc.next();
		String E =sc.next();
		char [] o = O.toCharArray();
		char [] e = E.toCharArray();
		for(int i=0;i<o.length;i++) {
			System.out.print(o[i]);
			if(o.length!=e.length && i==o.length-1)break;
			System.out.print(e[i]);
		}
		sc.close();
	}
}

Measured memory_bytes: 21972
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProblemA
{
    class Program
    {
        static void Main(string[] args)
        {
            var read = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var N = read[0];
            var K = read[1];
            if (K == 1)
                Console.WriteLine(0);
            else
                Console.WriteLine(N - K);
        }
    }
}


Measured memory_bytes: 13396
//
// Created by Mahmoud Rashad on 11/27/19.
//

#include <bits/stdc++.h>


using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<pair<ii, ii>> vii;

const int MAXN = 1003;
int vis[MAXN];
int mark[MAXN], checkID;
vector<int> adjList[MAXN];
vector<int> inProgress;
bool ret;


bool check(int x) {
//    cout << x << endl;
    ++checkID;
    mark[x] = checkID;
    inProgress.push_back(x);
    for (int i = (int)inProgress.size() - 2; inProgress[i] != x; --i)
        mark[inProgress[i]] = checkID;
    int i;
    for (i = (int)inProgress.size() - 2; inProgress[i] != x; --i) {
        int u = inProgress[i];
        for (int v : adjList[u]) {
            if (mark[v] == checkID && v != inProgress[i + 1]) {
                inProgress.pop_back();
                return false;
            }
        }
    }
    for (int v : adjList[x]) {
        if (mark[v] == checkID && v != inProgress[i + 1]) {
            inProgress.pop_back();
            return false;
        }
    }
    return true;
}

void dfs(int u) {
    vis[u] = 1;
    inProgress.push_back(u);
    for (int v : adjList[u]) {
        if (vis[v] == 1) {
//            cout << v << endl;
            ret = check(v);
            if (ret)
                return;
        } else if (vis[v] == 0) {
            dfs(v);
            if (ret)
                return;
        }
    }
    inProgress.pop_back();
    vis[u] = 2;
}

int main() {
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.out", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;


    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);
    }

    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dfs(i);
            if (ret) {
                vector<int> ans;
                for (int i = (int)inProgress.size() - 2; inProgress[i] != inProgress.back(); --i)
                    ans.push_back(inProgress[i]);
                ans.push_back(inProgress.back());
                cout << ans.size() << '\n';
                reverse(ans.begin(), ans.end());
                for (int x : ans)
                    cout << x << '\n';
                return 0;
            }
        }
    }

    cout << -1 << '\n';

    return 0;
}

Measured memory_bytes: 384
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def main():
    N, M = map(int, input().split())
    
    if N == 1 and M == 1:
        print(1)
        sys.exit()
    
    if N == 1:
        print(M-2)
        sys.exit()
        
    if M == 1:
        print(N-2)
        sys.exit()
        
    if N == 2 and M == 2:
        print(0)
        sys.exit()
    
    if N == 2 or M == 2:
        print(0)
        sys.exit()
        
    total = N*M
    total = total - (2*N)
    total = total - (2*M)
    total += 4
    
    print(total)
	
if __name__ == "__main__":
	main()


Measured memory_bytes: 38256
#include <iostream>
#include <string>

using namespace std;

int main(){
    int n;

    cin >> n;

    int first = n % 10;

    string str;
    switch(first){
        case 2:
        case 4:
        case 5:
        case 7:
        case 9:
            str = "hon";
            break;
        case 0:
        case 1:
        case 6:
        case 8:
            str = "pon";
            break;
        case 3:
            str = "bon";
            break;
    }

    cout << str << endl;

    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << '>' << #x << ':' << x << endl;

int main() {
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	for (int i = 1; i <= b; i++) {
		if (i * a % b == c)
			return printf("YES\n"), 0;
	}
	printf("NO\n");
}


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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;

const int CASES = 3;

void solve(){
    ll A, B, C, K; cin >> A >> B >> C >> K;
    if(K % 2 != 0){
        cout << B - A << endl;
    }
    else{
        cout << A - B << endl;
    }
}

int main() {
    #ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
    #else

    solve();

    #endif
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
int fa[100010];
long long dis[100010];
int n, m;

void init()
{
	memset(dis, 0, sizeof(dis));
	for (int i = 0; i <= n; i++) fa[i] = i;
}

void find(int x)
{
	if (fa[x] == x) return;
	find(fa[x]);
	dis[x] += dis[fa[x]], fa[x] = fa[fa[x]];
}

int main()
{
	int i, j;
	scanf("%d%d", &n, &m);
	init();
	for (i = 1; i <= m; i++)
	{
		int u, v;
		long long d;
		scanf("%d%d%lld", &u, &v, &d);
		find(u);
		find(v);
		int f1 =fa[u] , f2 =fa[v] ;
		if (f1 != f2)
		{
			fa[f2] = f1;
			dis[f2] = dis[u] + d - dis[v];
		}
		else
		{
			if (dis[v] - dis[u] != d)
			{
				printf("No\n");
				return 0;
			}
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 1408
s = list(input())

S = set(s)
res = 0
for k in S:
	t = s[::]
	while len(set(t)) != 1:
		t.pop()
		for i in range(len(t) - 1):
			if t[i] == k or t[i + 1] == k:
				t[i] = k
			else:
				t[i] = t[i]
	ma = len(t)
	res = max(res, len(t))

print(len(s) - res)

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         INT_MAX
#define MOD         (1000000007LL)

using LL  = long long;
// }}}

int main() {
    std::ios::sync_with_stdio(false);
    int n;cin >> n;
    string s;cin >> s;
    int ans = 0;
    int x = 0;
    for(auto c : s){
        if(c == 'I'){
            x++;
        }else{
            x--;
        }
        ans = max(ans, x);
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

template <class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')
    cerr<<*sdbg++;
  cerr<<"="<<h<<","; 
  _dbg(sdbg+1, a...);
}

template<class T> ostream & operator<<(ostream & os, vector<T> V){
  os<<"[";
  for(auto vv: V) os << vv <<",";
  return os << "]";
}
template<class L, class R> ostream & operator <<(ostream & os, pair<L,R> P){
  return os <<"("<<P.first <<","<<P.second <<")";
}

#ifdef DEBUG
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0}, INF = 1e9;

int n, m, k;
char row[1000005];
int startX, startY, stopX, stopY;
vector<vector<char>> board;
vector<vector<int>> dist;

void BFS(int startX, int startY) {
    dist[startX][startY] = 0;
    queue<pair<int, int> > Q;
    Q.push({startX, startY});
    while (!Q.empty()) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= k; j++) {
                int xx = x + dx[i] * j;
                int yy = y + dy[i] * j;
                if (board[xx][yy] == '@' || dist[xx][yy] <= dist[x][y]) {
                    break;
                }
                if (dist[xx][yy] == dist[x][y] + 1) {
                    continue;
                }
                dist[xx][yy] = dist[x][y] + 1;
                Q.push({xx, yy});
            }
        }
    }
}

int main() {
    
    scanf("%d %d %d", &n, &m, &k);
    
    scanf("%d %d %d %d", &startX, &startY, &stopX, &stopY);
    
    board = vector<vector<char>>(n + 2, vector<char>(m + 2, '@'));
    dist = vector<vector<int>>(n + 2, vector<int>(m + 2, INF));
    for (int i = 1; i <= n; i++) {
        scanf("%s", &row[1]);
        for (int j = 1; j <= m; j++) {
            board[i][j] = row[j];
        }
    }
    
    BFS(startX, startY);
    
    if (dist[stopX][stopY] == INF) {
        printf("-1\n");
        return 0;
    }
    
    printf("%d\n", dist[stopX][stopY]);
    
    return 0;
}


Measured memory_bytes: 21928
N, A, B = map(int, input().split())
X = list(map(int, input().split()))
D = [0]
for i in range(N-1):
    D.append(X[i+1]-X[i])

ans = 0
for i in range(1, N):
    ans += min(A*D[i], B)

print(ans)

Measured memory_bytes: 14252
D = int(input())
c = list(map(int,input().split()))
s = [list(map(int, input().split())) for l in range(D)]
last = [0]*26

def score_down(d):
    ans = 0
    for i in range(26):
        ans += c[i]*(d - last[i])
    return ans

for d in range(D):
    score = [(s[d][i] - score_down(d+1)) for i in range(26)]
    t = score.index(max(score))
    print(t+1)
    last[t] = d+1

Measured memory_bytes: 9324
#include <stdio.h>

int main(void)
{
int h;
int w;
char c[100];
int i;
int j;
scanf("%d%d",&h,&w);

for(i=0;i<h;i++){
	scanf("%s",c);
	printf("%s\n%s\n",c,c);
	
}

	return 0;
}

Measured memory_bytes: 128
/*input
6
382253568 723152896 37802240 379425024 404894720 471526144
*/
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin>>n;
	ll foo;
	ll ans=66;
	while(n--)
	{
		cin>>foo;
		ll cnt=0;
		while((foo&1)==0)
		{
			foo/=2;
			cnt++;
		}
		ans=min(ans,cnt);
	}
	cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

queue<pair<pp,int>> q;

int dx[6] = {1, 0, -1, -2, 2, 0};
int dy[6] = {1, -1, 0, -2, 0, 2};

set<pp> vis;

int main()
{
	int a, b, c; read(a, b, c);
	q.emplace(pp{b-a, c-a}, 0);
	vis.emplace(b-a, c-a);
	while(q.size()){
		int a, b; tie(a, b) = q.front().x;
		int d = q.front().y;
		q.pop();
		if(a==0 && b==0){
			printf("%d\n", d);
			return 0;
		}
		for(int dd=0; dd<6; ++dd){
			int nx=a+dx[dd];
			int ny=b+dy[dd];
			if(vis.find(pp{nx, ny}) == vis.end()){
				vis.insert(pp{nx, ny});
				q.emplace(pp{nx, ny}, d+1);
			}
		}
	}
	return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
  #include <stdlib.h>
  int puzle[3][3];
  int tmp[3][3];
  int d1[4]={0,1,0,-1};
  int d2[4]={1,0,-1,0};
 
  void empty(int *x,int *y){
    int i,j;
    for(i=0;i<3;i++){
      for(j=0;j<3;j++){
        if(!puzle[i][j]){
    *x=j;
    *y=i;
    return;
        }
      }
    }
  }
 
  void swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
  }
 
  int cal(){
    int a,i,sum=0;
    for(i=0;i<9;i++){
      a=puzle[i/3][i%3];
      if(a){
        a--;
        sum += abs(i/3-a/3) + abs(i%3-a%3);
      }
    }
    return sum;
  }
 
  int dfs(int x,int y,int p,int dep,const int lim){
    int i,h,n1,n2,res;
    h=cal();
    if(h==0){
      return dep;
    }
    if(dep+h > lim){
      return -1;
    }
    for(i=0;i<4;++i){
      n1=x+d1[i];
      n2=y+d2[i];
 
      if(~p && i==(p+2)%4)
        continue;
      if(!(0 <= n1 && n1 < 3 && 0 <= n2 && n2 < 3))
        continue;
      swap(&puzle[y][x],&puzle[n2][n1]);
      res=dfs(n1,n2,i,dep+1,lim);
 
      if(~res){
        return res;
      }
      swap(&puzle[y][x],&puzle[n2][n1]);
    }
    return -1;
  }
 
  int main(){
    int ans,x,y,l,i,j;
 
    for(i=0;i<3;i++){
      for(j=0;j<3;j++){
        scanf("%d",&puzle[i][j]);
      }
    }
    empty(&x,&y);
    for(l=0;l<100;l++){
      for(i=0;i<3;i++){
        for(j=0;j<3;j++){
    tmp[i][j]=puzle[i][j];
      }
    }
      ans=dfs(x,y,-1,0,l);
      if(ans!=-1){
        printf("%d\n",ans);
        break;
      }
      for(i=0;i<3;i++){
        for(j=0;j<3;j++){
    puzle[i][j]=tmp[i][j];
      }
      }
      ans=-1;
      if(l==99){
        printf("%d\n",ans);
    }
    }
    return 0;
  }



Measured memory_bytes: 2096
package main

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

func main() {
	io := newIo()
	defer io.Flush()
	N := io.NextInt()
	F := make([]int, N)
	P := make([][11]int, N)
	for i := 0; i < N; i++ {
		x := 0
		for j := uint(0); j < 10; j++ {
			if io.NextInt() == 1 {
				x += (1 << j)
			}
		}
		F[i] = x
	}
	for i := 0; i < N; i++ {
		for j := 0; j < 11; j++ {
			P[i][j] = io.NextInt()
		}
	}
	bitMax := 1 << 10
	var maxPoint int
	for bit := 1; bit < bitMax; bit++ {
		point := 0
		for i, f := range F {
			count := bitCount(f & bit)
			point += P[i][count]
		}
		if bit == 1 || point > maxPoint {
			maxPoint = point
		}
	}
	fmt.Println(maxPoint)
}

func bitCount(bit int) int {
	bit = bit - ((bit >> 1) & 0x55555555)
	bit = (bit & 0x33333333) + ((bit >> 2) & 0x33333333)
	bit = (bit + (bit >> 4)) & 0x0f0f0f0f
	bit = bit + (bit >> 8)
	bit = bit + (bit >> 16)
	return bit & 0x3f
}

type io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func newIo() *io {
	return &io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *io) PrintLn(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func (io *io) PrintIntLn(a []int) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func (io *io) PrintStringLn(a []string) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func log(name string, value interface{}) {
	fmt.Fprintf(os.Stderr, "%s=%+v\n", name, value)
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tii;
typedef long long ll;
#define rep(i,s,n) for(int i=(int)(s);i<(int)(n);i++)


int N,M;
int par[200010];
int rnk[200010];

void init(int n){
  for(int i=0;i<n;i++){
    par[i] = i;
    rnk[i] = 0;
  }
}

int find(int x){
  if(par[x]==x) return x;
  return par[x] = find(par[x]);
}

void unite(int x,int y){
  int nx = find(x);
  int ny = find(y);
  if(nx==ny) return;
  
  if(rnk[nx]<rnk[ny]){
    par[nx] = ny;
  }else{
    par[ny] = nx;
    if(rnk[nx]==rnk[ny]) rnk[nx]++;
  }
}

bool same(int x,int y){
  return find(x)==find(y);
}

int main(){
  cin >> N >> M;
  init(N);
  for(int i=0;i<M;i++){
    int x,y;
    cin >> x >> y;
    unite(x,y);
  }
  map<int,int> mp;
  int ans = 0;
  for(int i=0;i<N;i++){
    mp[find(i)]++;
    ans = max(ans,mp[find(i)]);
  }
  cout << ans << endl;
 
}

Measured memory_bytes: 14372
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-5;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
    int n;cin>>n;
    string a,b,c;cin>>a>>b>>c;
    int ans=0;
    for(int i=0;i<n;i++){
        if(a[i]==b[i]&&b[i]==c[i]){
            continue;
        }else if(a[i]==b[i]||b[i]==c[i]||a[i]==c[i]){
            ans++;
        }else{
            ans+=2;
        }
    }  
    cout<<ans<<endl;
}

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

using namespace std;
void swap(int &a, int &b);

int main()
{
	int H[300], W[300];
	int count = 0;
	while (true)
	{
		cin >> H[count] >> W[count];
		if (H[count] == 0 && W[count] == 0)
			break;
		count++;
	}

	for (int i = 0; i < count; ++i)
	{
		for (int j = 0; j < H[i]; ++j)
		{
			for (int k = 0; k < W[i]; ++k)
			{
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}

	return 0;
}




Measured memory_bytes: 3068
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            String s = in.nextString();

            out.println(s.replaceAll("1", "2")
                    .replaceAll("9", "1")
                    .replaceAll("2", "9"));
        }

    }

    static class InputReader {
        private BufferedReader br;
        private StringTokenizer st;

        public InputReader(InputStream inputStream) {
            br = new BufferedReader(new InputStreamReader(inputStream));
            st = new StringTokenizer("");
        }

        public String nextString() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine(), " ");
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return st.nextToken();
        }

    }
}



Measured memory_bytes: 21460
import java.util.*;
public class Main{
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in);
      int a = sc.nextInt();
      int b = sc.nextInt();
      int c = sc.nextInt();
      int n = sc.nextInt();
      int count = 0;

      for(int i = 0;i<=a;i++){
        for(int j = 0;j<=b;j++){
          for(int k = 0;k<=c;k++){
            if(n == 500*i + 100*j + 50*k){
				count++;
            }
          }
        }
      }
	System.out.println(count);
    }
}

Measured memory_bytes: 23508
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll n;
    cin >> n;
    ll cnt = 0;
    for(int i = 1; i <= n; i++){
        if(i % 3 != 0 && i % 5 != 0)
        cnt += i;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=1e5+5;
ll dp[N][2];
char s[N];
int main()
{
    scanf("%s",s+1);
    int l=strlen(s+1);
    dp[0][0]=1;
    for(int i=1;i<=l;i++)
    {
        if(s[i]=='1')
        {
            dp[i][0]=dp[i-1][0]*2%mod;
            dp[i][1]=(dp[i-1][1]*3+dp[i-1][0])%mod;
        }
        else
        {
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][1]*3%mod;
        }
    }
    printf("%lld\n",(dp[l][1]+dp[l][0])%mod);
}


Measured memory_bytes: 1920
# -*- coding: utf-8 -*-


if __name__ == '__main__':

    n = int(input())
    M = [list(map(int, input().split(" ")[1:])) for _ in range(n)]

    color = [0] * n
    d = [float("inf")] * n
    p = [None] * n

    def prim():
        d[0] = 0
        p[0] = -1

        while True:
            mincost = float("inf")
            for i in range(n):
                if color[i] != 2 and d[i] < mincost:
                    mincost = d[i]
                    u = i

            if mincost == float("inf"):
                break

            color[u] = 2

            for v in range(n):
                if color[v] != 2 and M[u][v] != -1:
                    if M[u][v] < d[v]:
                        d[v] = M[u][v]
                        p[v] = u
                        color[v] = 1

    prim()
    sum = 0
    for i in range(n):
        if p[i] != -1:
            sum += M[i][p[i]]

    print(sum)



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

int main()
{
	int w,h;
	while(cin>>h>>w){
		if(w==0 && h==0) break;
		const int d=h*h+w*w;
		int min_d=1000*1000,min_h=1000;
		int ans_w,ans_h;
		for(int nw=1;nw<=200;nw++){
			for(int nh=1;nh<nw;nh++){
				const int nd=nw*nw+nh*nh;
				if(d>nd || (nd==d && h>=nh)) continue;
				if(min_d>nd || (min_d==nd && nh<min_h)){
					min_d=nd;
					min_h=nh;
					ans_w=nw;
					ans_h=nh;
				}
			}
		}
		cout<<ans_h<<" "<<ans_w<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
//      https://youtu.be/X_hMZYDMps4

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

typedef long long ll;
typedef long double ld;
typedef long long unsigned llu;
typedef pair<long long, long long> pll;
const long long inf = 2000000000000000000LL;    // 2e18
#define pi                  acos(-1.0)
#define fast                ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define nl                  "\n"
#define ff                  first
#define ss                  second
#define pb                  push_back
#define pf                  push_front
#define all(x)              x.begin(),x.end()
#define debug(x)            cout<<"debug "<<x<<"\n"

int main()
{
    fast;
    ll t,i,j,k,l,m,n,o,p,q,temp,ans=0,flag=0,mod=1000000007,odd=0,even=0;
    cin>>n;
    vector<pll>v(n);
    for(i=0;i<n;i++){
        cin>>v[i].ff;
        v[i].ss=i+1;
    }
    sort(all(v));
    for(i=0;i<n;i++) cout<<v[i].ss<<" ";
}


Measured memory_bytes: 4780
def calcManhattanDistance(student, checkpoint):
    return abs(student[0] - checkpoint[0]) + abs(student[1] - checkpoint[1])


if __name__ == "__main__":
    # input process
    N, M = map(int, input().split())
    students = [list(map(int, input().split())) for i in range(N)]
    checkpoints = [list(map(int, input().split())) for i in range(M)]

    # calculation process
    for student in students:
        distance_list = []

        for checkpoint in checkpoints:
            distance_list.append(calcManhattanDistance(student, checkpoint))

        # print the first index(+1) of minimum value
        minval = min(distance_list)
        print(distance_list.index(minval) + 1)

    # END

Measured memory_bytes: 3064
import sys
from string import ascii_lowercase as a2z

input = sys.stdin.readline


def main():
    S = input().rstrip()

    ans = 100
    for al in a2z:
        if al not in S:
            continue
        i = 0
        max_cost = 0
        for j, s in enumerate(S + al):
            if s == al:
                cost = j - i
                if cost > max_cost:
                    max_cost = cost
                i = j + 1
        if max_cost < ans:
            ans = max_cost

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) rep(i,v.size())cout<<v[i]<<(i==v.size()-1?"\n":" ");
#define vout(v) VOUT(v,z);
#define vdbg(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL)
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
// template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
// template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
bool is_palindrome(string s){return s == string(s.rbegin(),s.rend());}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) { a = b; return true; }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) { a = b; return true; }
    return false;
}


int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long N;
    scanf("%lld",&N);

    // ll ma=0;

    auto f = [=](ll n) { return floor(A*n*1.0/B) - A*floor(n*1.0/B); };
    cout << f(min(N,B-1)) << endl;

    // if(B-1<=N){
    //     ll b = B-1;
    //     cout << floor(A*b*1.0/B) - A*floor(b*1.0/B) << endl;
    // }else{
    //     ll b = N;
    //     cout << floor(A*b*1.0/B) - A*floor(b*1.0/B) << endl;
    // }

    return 0;
}


Measured memory_bytes: 3812
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
const ll MOD = 998244353;

ll power(ll x, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) {
      res = res * x % MOD;
    }
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}

ll N;
vector<ll> D;
ll d1;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  D.resize(N, 0);
  for (ll i = 0; i < N; i++) {
    ll d;
    cin >> d;
    D[d]++;
    if (i == 0) {
      d1 = d;
    }
  }

  bool flag = false;
  bool flag2 = false;
  if (d1 != 0) {
    flag = true;
  }
  if (D[0] > 1) {
    flag = true;
  }
  for (ll i = 0; i < N; i++) {
    if (flag2 && D[i] > 0) {
      flag = true;
    }
    if (D[i] == 0) {
      flag2 = true;
    }
  }
  if (flag) {
    cout << 0 << endl;
    return 0;
  }

  if (N == 1) {
    cout << 1 << endl;
    return 0;
  }

  ll ans = 1;
  for (ll i = 2; i < N; i++) {
    if (D[i] == 0) {
      break;
    }
    ans *= power(D[i - 1], D[i]);
    ans %= MOD;
  }

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

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

typedef long long i64;
const int NMAX = 100010;

struct Str {
	int vmin, vmax, other;
	i64 sp, suma;
	bool operator< (const Str& oth) {
		return sp > oth.sp;
	}
};
Str exams[NMAX];
int n, X;
i64 to_win;

void calc_exams()
{
	for (int i = 1; i <= n; i++) {
		i64 sact = 1LL * exams[i].other * exams[i].vmin;
		to_win += sact;
		sact += 1LL * (X - exams[i].other) * exams[i].vmax;
		exams[i].sp = sact;
	}
	sort(exams + 1, exams + n + 1);
	for (int i = 1; i <= n; i++)
		exams[i].suma = exams[i].sp, exams[i].sp += exams[i - 1].sp;
}

i64 TryExam(int id)
{
	// vreau sa iau cat mai putin din examul id
	int ans = 0, ok = 1;
	auto verif = [&](int poz) {
		return exams[poz].sp - (id <= poz ? exams[id].suma : 0);
	};
	for (int p = 1; p; p = (ok ? 2 * p : p / 2)) {
		if (ans + p <= n && verif(ans + p) < to_win - exams[id].suma)
			ans += p;
		else
			ok = 0;
	}
	if (verif(ans) < to_win - exams[id].suma)
		ans++;

	i64 tact = 1LL * (ans - (id <= ans ? 1 : 0)) * X;
	i64 left = to_win - verif(ans);
	if (left < 0)
		return tact;
	if (1LL * exams[id].vmin * exams[id].other >= left)
		tact += (left + exams[id].vmin - 1) / exams[id].vmin;
	else {
		tact += exams[id].other;
		left -= 1LL * exams[id].vmin * exams[id].other;
		tact += (left + exams[id].vmax - 1) / exams[id].vmax;
	}
	return tact;
}

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

	cin >> n >> X;
	for (int i = 1; i <= n; i++)
		cin >> exams[i].other >> exams[i].vmin >> exams[i].vmax;

	calc_exams();

	i64 best = 1e18;
	for (int i = 1; i <= n; i++)
		best = min(best, TryExam(i));

	cout << best << '\n';

	return 0;
}


Measured memory_bytes: 3328
#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;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

string s;

int64 ten(int64 x, int64 d) {
  REP(i, d) x *= 10;
  return x;
}

int64 stoi_my(string s) {
  int64 ret = 0;
  REP(i, s.size()) ret = ret*10 + s[i]-'0';
  return ret;
}

int64 score(int64 a) {
  int64 ss = stoi_my(s);
  return min(abs(ss-a), ten(1, s.size()) - abs(ss-a));
}

int main(void) {
  vector<int64> v(10, 0);
  cin >> s;
  REP(i, s.size()) {
    v[i] = i+1;
  }
  sort(all(v));
  int64 ans = 0;
  do {
    string res(s.size(), '.');
    REP(i, v.size()) {
      if (v[i] != 0) {
        res[v[i]-1] = '0' + i;
      }
    }
    if (score(ans) <= score(stoi_my(res))) {
      if (score(ans) < score(stoi_my(res)) || ans > stoi_my(res))
        ans = stoi_my(res);
    }
  } while (next_permutation(all(v)));
  cout << setfill('0') << setw(s.size()) << ans << endl;
}


Measured memory_bytes: 3212
#include<bits/stdc++.h>
using namespace std;
int CntO,H,W;
int grid[510][510];
vector<int> ans[4];
bool All=true;
const int dx[]={1,0},dy[]={0,1};
void input()
{
	cin>>H>>W;
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++)
		{
			cin>>grid[i][j];
			All^=(grid[i][j]%2);
		}
	return ;
}
void output()
{
	cout<<CntO<<endl;
	for(int i=0;i<CntO;i++)
		for(int j=0;j<4;j++)
			cout<<ans[j][i]<<(" \n"[j==3]);
	return ;
}
void Insert(int x1,int y1,int x2,int y2)
{
	CntO++;
	ans[0].push_back(x1);
	ans[1].push_back(y1);
	ans[2].push_back(x2);
	ans[3].push_back(y2);
	return ;
}
bool valid(int x,int y)
{
	return (x>=0&&x<H&&y>=0&&y<W);
}
int main()
{
	input();
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++)
			if(grid[i][j]%2)
				for(int k=0;k<2;k++)
				{
					int tox=dx[k]+i,toy=dy[k]+j;
					if(valid(tox,toy))
					{
						Insert(i+1,j+1,tox+1,toy+1);
						grid[i][j]--;
						grid[tox][toy]++;
						break;
					}
				}
	output();
	return 0;
}

Measured memory_bytes: 5220
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc =new Scanner(System.in);
int numberA = sc.nextInt();
int numberB = sc.nextInt();
if(numberA > 8){
System.out.println(":(");}
else if(numberB > 8){
System.out.println(":(");}
else{
System.out.println("Yay!");}
}
}

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

void dfs(int node,vector<vector<int>> &G,vector<bool> &vis,vector<int> &dp){
	vis[node]=true;
  	dp[node]=0;
  	for(int child:G[node]){
     	if(!vis[child])
          	dfs(child,G,vis,dp);
      	dp[node]=std::max(dp[node],dp[child]+1);
    }
}

int main(){
    int N,M;
    cin>>N>>M;
  	vector<vector<int>> G(N+1);
  	while(M--){
    	int a,b;
      	cin>>a>>b;
      	G[a].push_back(b);
    }
  	vector<bool> vis(N+1,false);
	vector<int> dp(N+1);
  	for(int i=1;i<=N;i++){
    	if(!vis[i]){
        	dfs(i,G,vis,dp);
        }
    }
    cout<<*max_element(dp.begin(),dp.end());
    return 0;
}

Measured memory_bytes: 12500