akhauriyash/Code-Regression huggingface dataset:
N, M = gets.chomp.split.map(&:to_i) # No. of islands, bridges
bridges = []
M.times do
  bridges.push gets.chomp.split.map(&:to_i)
end
#p bridges

combi_h = Hash.new {|h, n| h[n] = n * (n - 1) / 2}
ns = [combi_h[N]]
$par = (0..(N-1)).to_a
$num = [1] * N

def merge(r1, r2)
  if $num[r1] < $num[r2] then r1, r2 = r2, r1 end
  $par[r2] = r1
  $num[r1] = $num[r1] + $num[r2]
  $num[r2] = 0
end

def is_root?(n) $par[n] == n end
  
def get_root(n)
  if is_root?(n)
    n
  elsif is_root?($par[n])
    $par[n]
  else
    r = get_root($par[n])
    $par[n] = r
    r
  end
end

inconv = combi_h[N]
(M-1).downto(1).each do |i|
  bridge = bridges[i]
  r1 = get_root(bridge[0]-1)
  r2 = get_root(bridge[1]-1)
  if r1 != r2
    n1 = $num[r1]
    n2 = $num[r2]
    merge(r1, r2)
    inconv -= combi_h[n1+n2] - combi_h[n1] - combi_h[n2]
  end
  ns.push inconv
end

ns.reverse.each do |n| print("#{n}\n") end

Measured memory_bytes: 20276
#include<iostream>
#include<string.h>
#include<cstring>
#include<cmath>
#include<ctype.h>
using namespace std;
typedef long long ll;

int main(void)
{
    int A,B,N;
    scanf("%d%d%d",&N,&A,&B);
    if(N==1)
    {
        if(A==B)
            printf("1\n");
        else
            printf("0\n");
    }
    else
    {
        if(A>B)
            printf("0\n");
        else
            printf("%lld\n",(long long )(B-A)*(N-2)+1);
    }
    return 0;
}


Measured memory_bytes: 256
#include <cassert>
#include <algorithm>
#include <cctype>
#include <complex>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <tuple>
#include <typeinfo>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REPD(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define PB(e) push_back(e)
#define FOREACH(i, c) for(auto i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define BIT(n, m) (((n) >> (m)) & 1)

typedef long long ll;

template <typename S, typename T> ostream &operator<<(ostream &out, const pair<S, T> &p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}

template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "[";
  REP(i, v.size()){
    if (i > 0) out << ", ";
    out << v[i];
  }
  out << "]";
  return out;
}

typedef pair<ll, int> P;
const int MAX = 100010;
vector<int> G[MAX];
vector<ll> S[MAX];
vector<ll> Y[MAX];

vector<ll> dijkstra(const vector<int> G[], const vector<ll> C[], int s, int n) {
  vector<ll> cost(n + 1, 1e18);
  cost[s] = 0;
  
  auto queue = priority_queue<P, vector<P>, greater<P>>();
  queue.push(P(0, s));
  while (!queue.empty()) {
    auto p = queue.top(); queue.pop();
    int v = p.second;
    ll c = p.first;
    REP(i, G[v].size()) {
      int w = G[v][i];
      ll nc = C[v][i] + c;
      if (nc < cost[w]) {
        cost[w] = nc;
        queue.push(P(cost[w], w));
      }
    }
  }
  return cost;
}

int main(int argc, char *argv[])
{
  int n, m, s,t;
  cin >> n >> m >> s >> t;
  REP(i, m) {
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    G[u].push_back(v);
    Y[u].push_back(a);
    S[u].push_back(b);
    
    G[v].push_back(u);
    Y[v].push_back(a);
    S[v].push_back(b);
  }
  auto sy = dijkstra(G, Y, s, n);
  auto ts = dijkstra(G, S, t, n);

  vector<ll> res(n + 2, 1e18);
  for (int i = n; i >= 1; i--) {
    res[i] = min(res[i + 1], sy[i] + ts[i]);
  }
  for (int i = 1; i <= n; i++) {
    cout << 1000000000000000LL - res[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 21708
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<sstream>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;


int main()
{
	string s;
	cin >>s;
	if(s == "SUN")
		cout << 7 <<endl;
	else if(s == "MON")
		cout << 6 <<endl;
	else if(s == "TUE")
		cout << 5 <<endl;
	else if(s == "WED")
		cout << 4 <<endl;
	else if(s == "THU")
		cout << 3 <<endl;
	else if(s == "FRI")
		cout << 2 <<endl;
	else if(s == "SAT")
		cout << 1 <<endl;
	return 0;
}


Measured memory_bytes: 256
// Problem : E - Coprime
// Contest : AtCoder - AtCoder Beginner Contest 177
// URL : https://atcoder.jp/contests/abc177/tasks/abc177_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

/*ヽ｀、ヽ｀｀、ヽ｀ヽ｀、、ヽ ｀ヽ 、ヽ｀🌙｀ヽヽ｀ヽ、ヽ｀
ヽ｀、ヽ｀｀、ヽ 、｀｀、 ｀、ヽ｀ 、｀ ヽ｀ヽ、ヽ ｀、ヽ｀｀、
ヽ、｀｀、｀、ヽ｀｀、 、ヽヽ｀、｀、、ヽヽ、｀｀、 、 ヽ｀、
ヽ｀｀、 ヽ｀ヽ｀、、ヽ ｀ヽ 、 🚶ヽ｀｀｀｀ヽヽヽ｀、、ヽ｀、、ヽ*/
#include <bits/stdc++.h> 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long   ll;
typedef long double ld;
typedef complex< ld > cd;
 
typedef pair<int, int> pi;
typedef pair<ll, ll>   pl;
typedef pair<ld, ld>   pd;
 
typedef vector< int > vi;
typedef vector< ld >  vd;
typedef vector< ll >  vl;
typedef vector< pi >  vpi;
typedef vector< pl >  vpl;
typedef vector< cd >  vcd;
 
#define l00p(i, a, b) for (int i=a; i<(b); i++)
#define loop(i, a)    for (int i=0; i<(a); i++)
#define rep1(i, a, b) for (int i = (b)-1; i >= a; i--)
#define rep(i, a)     for (int i = (a)-1; i >= 0; i--)
#define trav(a, x)    for (auto& a : x)
#define uid(a, b)     uniform_int_distribution<int>(a, b)(rng)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f  first
#define s  second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
//#define MOD 998244353
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ld pii=3.14159265359; 
const int MOD = 1000000007;
const char nl = '\n';
const ll INF = 1e18;
const int MX = 1000001; //check the limits, dummy
vi a(1000001);
void SieveOfEratosthenes(ll n) 
{
  
    for (ll p=2; p<=n; p++) 
    { 
        if (!a[p]) 
        {
        	a[p]=p;
            for (ll i=p*p; i<=n; i += p) 
             	a[i]=p;   
        } 
    } 
} 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	int n ; 
    cin >> n ; 
    vi a(n) ; 
    vi cnt(1e6+1) ; 
    int x ; 
    loop(i,n) {
        cin >> a[i] ;  
        ++cnt[a[i]] ; 
 
    }
 
    int g = 0 ; 
    loop(i,n) {
        g = __gcd(g,a[i]) ; 
    }
    if(g>1) {
      cout << "not coprime"; 
      return 0 ; 
    }
 
    for(int i = 2 ; i < 1e6+1 ; ++i) {
        int tmp =0 ; 
        for(int j = i ; j < 1e6+1 ; j += i ) 
            tmp += cnt[j] ; 
        if(tmp > 1) {
            cout << "setwise coprime" ; 
            return 0 ; 
        }
    }
    cout << "pairwise coprime" ; 
    
 
    return 0; 
}
// read the question correctly (ll vs int)
// template by bqi343

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

using ll = long long;
#define ld long double
#define ull unsigned long long int

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  // (i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define ret return

typedef pair<int, int>    pii;
typedef vector<int>       vi;
typedef vector<vi>        vii;
typedef vector<long long> vl;

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

    // 入力
    int n;
    cin >> n;

    // 処理
    int ans = 1;
    while (n >= ans * 2) {
        ans *= 2;
    }

    // 出力
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=3e3+5,mod=1e9+7,inf=INT_MAX;
ld p[N],c[N];
vector<vector<int> > adj;
multiset<int> ms;
ld dp[N][N];
    int n;

ld solve(int ind,int left)
{
    if(ind==n)
        return 1;
    ld ans1=0,ans2=0;
    ld& r=dp[ind][left];
    if(r!=-1)return r;
    if(left>0)
        ans2=solve(ind+1,left-1)*(1-p[ind]);
    ans1=solve(ind+1,left)*(p[ind]);
    return r=ans1+ans2;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>p[i];
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)
            dp[i][j]=-1;
    }
    cout<<fixed<<setprecision(15)<<solve(0,n/2);

    return 0;
}


Measured memory_bytes: 145132
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <numeric>
#include <iomanip>
#include <limits>
#include <set>
#include <map>
#include <type_traits>
#include <cstdint>
#include <queue>
#define _USE_MATH_DEFINES
#include <math.h>
#include <sstream> // std::stringstream
#include <bitset>  // std::bitset<N>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

//素因数分解
void factoring(ll n, map<ll, ll>& mp) {
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			mp[i]++;
			n /= i;
		}
	}
	if (n != 1) mp[n]++;
}

//絶対値
template<class T, class U = std::make_unsigned_t<T>>
U SafeAbs( T x ) {
    return x < 0 ? -static_cast<uintmax_t>(x) : x;
}

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

//xのn乗
ll mod_pow(ll x, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
//xの逆元
ll mod_inv(ll x, ll mod) {//O(log(mod))
    return mod_pow(x, mod - 2, mod);
}

//nCr
ll ncr(ll n, ll r, ll mod){
	ll res=1;
	ll num=1,den=1;
	for(ll i=n;i>=n-r+1;i--){
		(den*=i)%=mod;
	}
	for(ll i=1;i<=r;i++){
		(num*=i)%=mod;
	}
	
	res=den*mod_inv(num,mod);

	return res%mod;
}


//二分探索
bool isOk(ll index, ll key,vector<ll> &a){
	
	if(a[index]>key){
		return true;
	}
	
	return false;
}

ll bin_search(ll key, vector<ll> &a){
	
	ll l=-1;
	ll r=a.size();

	while(abs(r-l)>1){
		ll mid = (l+r)/2;
		if(isOk(mid, key, a)){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	return r;
}

/*
//深さ優先探索
void dfs(vector<vector<ll>> &gra,vector<bool> &seen, ll v){

	seen[v]=true;

	for(auto next : gra[v]){
		if(seen[next]){
			continue;
		}

		dfs(gra,seen,next);
	}
	
}
*/

const ll MOD=1000000007;

ll min(ll a, ll b){
	if(a>=b){
		return b;
	}
	else{
		return a;
	}
}

bool compare_by_b(pair<ll, ll> a, pair<ll, ll> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}


void solve()
{
	ll ans;
	cin >> ans;
	if(ans==0){
		cout << 1 << endl;
	}
	else{
		cout << 0 << endl;
	}
}

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

Measured memory_bytes: 3680
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
using namespace std;

using Flow = int;

struct Edge {
	int src, dst;
	Flow cap;
};

typedef vector<vector<Edge>> Graph;
struct dinic {
	int n, s, t;
	std::vector<int> level, prog, que;
	std::vector<std::vector<Flow>> cap, flow;
	std::vector<std::vector<int>> g;
	Flow inf;
	dinic(const Graph &graph)
		: n(graph.size()),
		cap(n, std::vector<Flow>(n)),
		flow(n, std::vector<Flow>(n)),
		g(n, std::vector<int>()),
		inf(std::numeric_limits<Flow>::max() / 8) {
		for (int i = 0; i < n; i++) {
			for (auto &e : graph[i]) {
				int u = e.src, v = e.dst;
				Flow c = e.cap;
				cap[u][v] += c;
				cap[v][u] += c;
				flow[v][u] += c;
				g[u].push_back(v);
				g[v].push_back(u);
			}
		}
	}
	inline Flow residue(int u, int v) { return cap[u][v] - flow[u][v]; }
	Flow solve(int s_, int t_) {
		this->t = t_, this->s = s_;
		que.resize(n + 1);
		Flow res = 0;
		while (levelize()) {
			prog.assign(n, 0);
			res += augment(s, inf);
		}
		return res;
	}
	bool levelize() {
		int l = 0, r = 0;
		level.assign(n, -1);
		level[s] = 0;
		que[r++] = s;
		while (l != r) {
			int v = que[l++];
			if (v == t) break;
			for (const int &d : g[v])
				if (level[d] == -1 && residue(v, d) != 0) {
					level[d] = level[v] + 1;
					que[r++] = d;
				}
		}
		return level[t] != -1;
	}
	Flow augment(int v, Flow lim) {
		Flow res = 0;
		if (v == t) return lim;
		for (int &i = prog[v]; i < (int)g[v].size(); i++) {
			const int &d = g[v][i];
			if (residue(v, d) == 0 || level[v] >= level[d]) continue;
			const Flow aug = augment(d, std::min(lim, residue(v, d)));
			flow[v][d] += aug;
			flow[d][v] -= aug;
			res += aug;
			lim -= aug;
			if (lim == 0) break;
		}
		return res;
	}
};

int mat[501][501] = {};

signed main() {

	int n, m;
	string u;
	
	cin >> n >> m >> u;
	vector<int> a(n);

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

	Graph g(n + 2);

	for (int i = 0; n > i; i++) {
		if (u[i] == 'L') {
			g[n].push_back({n, i, 0});
			g[i].push_back({i, n + 1, a[i]});
		}
		else {
			g[n].push_back({ n, i, a[i] });
			g[i].push_back({ i, n + 1, 0 });
		}
	}

	

	for (int i = 0; m > i; i++) {
		int s, t, b;
		cin >> s >> t >> b;
		s--, t--;
		if (s > t) swap(s, t);

		mat[s][t] += b;
	}

	for(int i = 0; n > i; i++)
		for (int j = 0; n > j; j++) {
			if (mat[i][j] != 0) {
				g[min(i,j)].push_back({ min(i,j), max(i,j), mat[i][j] });
			}
		}

	dinic din(g);
	cout << din.solve(n, n + 1) << endl;


	return 0;
}


Measured memory_bytes: 5380
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int main(void){

    int N;      cin >> N;
    vector<int> p(N);
    for(int i = 0 ; i < N ; i++)        cin >> p[i];

    int count = 0;
    for(int i = 0 ; i < N ; i++)
        if(p[i] != i + 1)   count++;
    
    if(2 < count)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;


    return 0;
}

Measured memory_bytes: 256
N,M = gets.chomp.split(" ").map(&:to_i)
arr = []
N.times do |i|
  a,b = gets.chomp.split(" ").map(&:to_i)
  arr << [a,b]
end
arr = arr.sort_by{|x| x[0]}
cnt = M
i = 0
money = 0
while cnt > 0
  if cnt >= arr[i][1]
    money += arr[i][0] * arr[i][1]
    cnt -= arr[i][1]
  else
    money += arr[i][0] * cnt
    cnt = 0
  end
  i += 1
end
puts money

Measured memory_bytes: 23852
using System;
using System.Collections.Generic;
using System.Text;

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            var inputLine = Console.In.ReadLine();
            var inputs = inputLine.Split(new char[] { ' ', '\t', '　' });
            if (inputs.Length != 2)
            {
                return;
            }

            var a = int.Parse(inputs[0]);
            var b = int.Parse(inputs[1]);
            Func<int, bool> check = (int i) =>
            {
                if (i < -1000) return false;
                if (i > 1000) return false;
                return true;
            };
            if (false
                || check(a) == false
                || check(b) == false
                )
            {
                return;
            }

            var op = "==";
            if (a < b)
            {
                op = "<";
            }
            if (a > b)
            {
                op = ">";
            }

            Console.WriteLine("a {0} b", op);
        }
    }
}


Measured memory_bytes: 17944
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <vector>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int r;
  cin>>r;
  if(r<1200){
    cout<<"ABC"<<"\n";
  }
  else if(r<2800){
    cout<<"ARC"<<"\n";
  }
  else{
    cout<<"AGC"<<"\n";
  }
  return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <tuple>
#include <cassert>
#include <memory>
using namespace std;
typedef long long ll;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
 
bool check (string S)
{
    for (int i = 0; i < S.size() / 2; i++) {
        if (S[i] != S[S.size() - 1 - i]) {
            return false;
        }
    }
    return true;
}
 
int main ()
{
    string s1; cin >> s1;
    int N = (int)s1.size();
    string s2 = s1.substr(0, (N - 1) / 2);
    //string s3 = s1.substr((N + 3) / 2 - 1, N - (N + 3) / 2 + 1);
 
    if (check(s1) && check(s2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
 
    return 0;
}

Measured memory_bytes: 256
N = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))
r = sum(Bs)
for i in range(1, N):
  if As[i] == As[i-1]+1:
    r += Cs[As[i-1]-1]
print(r)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
template <class T> int size(const T &x) { return x.size(); }
const int INF = 2147483647;
#define rep(i,a,b) for (__typeof(a) i=(a); i<(b); ++i)
#define iter(it,c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)

int cnt[100100];
bool red[100100];
vii es;

int main() {
    int n, m;
    cin >> n >> m;
    rep(i,0,n) {
        cnt[i] = 1;
        red[i] = i == 0;
    }
    rep(i,0,m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        es.push_back(ii(a,b));
    }
    iter(it,es) {
        int a = it->first,
            b = it->second;
        cnt[b]++;
        if (red[a]) red[b] = true;
        if (--cnt[a] == 0) {
            red[a] = false;
        }
    }
    int res = 0;
    rep(i,0,n) {
        if (red[i]) {
            res++;
        }
    }
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 1912
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;
ll MOD = 1000000007;

// a^p
// 2^3 = 2 * 2^2
// 2^2 = 2 * (2^1)
// 2^1 = 2
ll modpow(ll a, ll p, ll mod) {
  if (p == 0) return 1;

  if (p % 2 == 0) {
    ll half = modpow(a, p / 2, mod) % mod;
    return half * half % mod;
  } else {
    return a * modpow(a, p - 1, mod) % mod;
  }
}

// nCa を求める
ll modCombination(ll n, ll a, ll mod) {
  if (n - a < a) {
    return modCombination(n, n - a, mod);
  }

  ll denominator = 1;  // 分母
  ll numerator = 1;    // 分子

  for (ll i = 0; i < a; i++) {
    denominator *= a - i;
    numerator *= n - i;
    denominator %= mod;
    numerator %= mod;
  }

  return numerator * modpow(denominator, mod - 2, mod) % mod;
}

class UnionFind {
 private:
  vector<ll> parents;

 public:
  UnionFind(ll n) : parents(n, -1) {}

  bool issame(ll x, ll y) { return root(x) == root(y); }

  bool merge(ll x, ll y) {
    if (issame(x, y)) return false;

    ll rx = root(x);
    ll ry = root(y);
    if (parents[rx] > parents[ry]) swap(rx, ry);
    // サイズ情報を更新
    parents[rx] += parents[ry];
    // yの親を更新
    parents[ry] = rx;

    return true;
  }

  ll size(ll x) { return -parents[root(x)]; }

 private:
  ll root(ll x) {
    if (parents[x] < 0) return x;
    // 根の親の値に木の(-)サイズの情報を入れる
    return parents[x] = root(parents[x]);
  }
};

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

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);

  ll N;
  cin >> N;
  vector<ll> B(N - 1);
  vector<ll> A(N);

  for (ll i = 0; i < N - 1; i++) {
    cin >> B[i];
  }

  A[0] = B[0];
  A[N - 1] = B[N - 2];

  for (ll i = 1; i < N - 1; i++) {
    A[i] = min(B[i], B[i - 1]);
  }

  ll ans = 0;
  for (auto a : A) {
    ans += a;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main(){
  ll N,W; cin >> N >> W;
  vector<ll> w(N), v(N);
  REP(i,N){
    cin >> w[i] >> v[i];
  }
  //重みを補正する, 0<=wi<=3
  ll d = w[0];
  REP(i,N) w[i] -= d;
  //dp[i][j][k]:i番目まで見て，j個使用，補正後の重みの和がkのとき価値の最大値
  vector<vector<vector<ll>>> dp(N+1, vector<vector<ll>>(N+1,vector<ll>(3*N+1,-1)));
  dp[0][0][0] = 0;

  REP(i,N) REP(j,N+1) REP(k,3*N+1) if(dp[i][j][k] != -1){
    dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k]);
    dp[i+1][j+1][k+w[i]] = max(dp[i+1][j+1][k+w[i]], dp[i][j][k]+v[i]);
  }

  ll ans = 0;
  REP(j,N+1){
    REP(k,min(W-j*d,3*N)+1){
      ans = max(ans,dp[N][j][k]);
    }
  }
  cout << ans << endl; 
}

Measured memory_bytes: 24960
#include<bits/stdc++.h>
#include<iomanip>
#define mins(a,b) a=min(a,b)
#define maxs(a,b) a=max(a,b)
template < typename T > std::string to_string( const T& n )
  {
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
  }
using namespace std;

const long long INF=9000000000000000;
const long long mod=1000000007;
typedef long long ll;

int main(){
  ll n,ans=0,k,m=0,x=0,y=0;
  cin>>n;
  cout<<3*n*n<<endl;
  
}


Measured memory_bytes: 256
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void debug(String str) {
        System.out.println(str);
    }
 
    public static void main(String[] args) {
 
        int N;
        int Q;
 
        Node[] nodes;
        Operation[] ope;
 
        try (Scanner sc = new Scanner(System.in)) {
            N = sc.nextInt();
            Q = sc.nextInt();
 
            nodes = new Node[N];
            ope = new Operation[Q];
 
            for (int i = 0; i < N; i++) {
                nodes[i] = new Node(i+1);
            }
 
            for(int i = 0; i < N-1; i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
 
                nodes[a - 1].nodeList.add(nodes[b - 1]);
                nodes[b - 1].nodeList.add(nodes[a - 1]);
            }
 
            for(int i = 0; i < Q; i++){
                int p = sc.nextInt();
                int x = sc.nextInt();
 
                Operation e = new Operation(p, x);
                ope[i] = e;
            }
 
            for(Operation o :ope){
                int p = o.p;
                int x = o.x;
                nodes[p - 1].addNum += x;
            }
 
            //深さ優先探索
            Deque<Node> queue = new ArrayDeque<Node>(N);
            nodes[0].visited = true;
            queue.add(nodes[0]);
            nodes[0].realNUm += nodes[0].addNum;
            Node n = null;
 
            while ((n = queue.peekLast()) != null) {
                //未訪問の隣接ノードを取得
                Node m = n.getUnVisitNode();
                //隣接ノードあり。
                if(m != null){
                    m.visited = true;
                    queue.add(m);
                    m.realNUm = m.addNum +n.realNUm;
                }else{
                    //隣接ノードなし
                    queue.pollLast();
                }
            }
            StringBuilder sb = new StringBuilder();
            for(Node noo :nodes){
                sb.append(noo.realNUm + " ");
            }
            System.out.println(sb.toString());
        }
    }
 
 
    public static class Node {
        long addNum = 0;
        long realNUm = 0;
        long id;
        boolean visited = false;
        List<Node> nodeList = new LinkedList<>();
        public Node(int id){
            this.id = id;
        }
 
        public Node getUnVisitNode(){
            Node result = null;
            for(Node n : nodeList){
                if(!n.visited){
                    result = n;
                    break;
                }
            }
            nodeList.remove(result);
            return result;
        }
 
        public void print(){
            System.out.println("["+id+"]:"+addNum +":"+realNUm);
        }
 
    }
 
    public static class Operation {
        int p;
        int x;
        public Operation(int p, int x) {
            this.p = p;
            this.x = x;
        }
    }
}

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

# define C continue;
# define R return

# define D double
# define I insert
# define ll long long
# define ld long double

# define ull unsigned long long
# define ui unsigned int

# define pb push_back
# define pf push_front

# define vi vector < int >
# define vc vector < char >
# define vs vector < string >
# define vb vector < bool >
# define vd vector < D >
# define vll vector < ll >
# define vull vector < ull >
# define vld vector < ld >

# define vvi vector < vector < int > >
# define vvb vector < vector < bool > >
# define vvc vector < vector < char > >
# define vvll vector < vector < ll > >
# define vvd vector < vector < D > >
# define vvld vector < vector < ld > >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()
# define allcomp(v) v.begin() , v.end() , comp
# define allrevcomp(v) v.rbegin() , v.rend() , comp

# define pii pair < int , int >
# define pll pair < ll , ll >
# define pld pair < ld , ld >
# define pDD pair < D , D >

# define vpld vector < pld >
# define vpii vector < pii >
# define vpll vector < pll >
# define vpDD vector < pDD >

# define vvpii vector < vector < pii > >
# define F first
# define S second
# define mp make_pair

# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);
# define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))

# define pp(n) printf("%.10Lf",n);
# define line cout<<"\n";

const ld pie = 3.14159265358979 ;
const ll mod = 1e9 + 7 ;

string vow = "aeiou";

void solve ( int test_case )
{
    int n ; cin >> n ;
    string s ; cin >> s ;

    char c = s[0] ;
    int i=0 ;

    int ans  = 1 ;
    for ( ; i < n ; i++ )
    {
        for ( ;  i < n && s[i] == c ; i++ ) ;
        if ( i == n ) break ;
        ans ++ ;
        c = s[i] ;
    }

    cout << ans ; line
}

int main()
{
    int t = 1;
    //cin >> t;

    for ( int i=0 ; i < t ; i++ ) solve(i);
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i =(b)-1;i>=(a);--i)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
typedef vector<int> vi;
const int mod = 1e9 + 7;
const int maxn = 2e6 + 10; 
int main(){
	double a,b,c,d;
	scanf("%lf%lf%lf%lf",&a,&b,&c,&d); 
	double t1 = c*30 + d/2;
	double t2 = d*6;
	double ang = (t1 - t2);
	
	printf("%.9lf",sqrt(a*a+b*b-2*a*b*cos(ang*3.1415926535898/180))); 
	return 0;
}


Measured memory_bytes: 4264
#include<stdio.h>

int H[251];





int main(){
	int i,n;	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&H[i]);
	}




	for(i=1;i<=n;i++){
		printf("node %d: key = %d, ",i,H[i]);
		if(i/2>=1)printf("parent key = %d, ",H[i/2]);
		if(i*2<=n)printf("left key = %d, ",H[i*2]);
		if(i*2+1<=n)printf("right key = %d, ",H[i*2+1]);

		printf("\n");
	}

	return 0;
}




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

typedef long long ll;
#define OO 1e9
using namespace std;

int main(){
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  int n, k;
  cin >> n >> k;
  int h[n];
  for(int i = 0;i < n;i++)
    scanf("%d", h + i);
  int dp[n];
  dp[n - 1] = 0;
  for(int i = n - 2;i >= 0;i--){
    dp[i] = 1e9;
    for(int j = i + 1;j <= i + k && j < n;j++){
      dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]));
    }
  }
  cout << dp[0];
}


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

using namespace std;

#define ll long long
#define ar array


int n;


void solve(){
    
    string s;

    cin >> s;

    if(islower(s.front())){
        cout << "a" <<endl;

    }
    else{
        cout << "A" << endl;
    }
}





int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Measured memory_bytes: 3612
n=int(input())
s=input()
#000~999からいくつ作れるか試す
num='0123456789'
ans=0
#候補の暗証番号を生成する
for first_num in num:
    for second_num in num:
        for third_num in num:
            temp_lock=first_num+second_num+third_num
            temp_cnt=0
            for i in s:
                if temp_cnt==0 and i==temp_lock[0]:
                    temp_cnt=1
                elif temp_cnt==1 and i==temp_lock[1]:
                    temp_cnt=2
                elif temp_cnt==2 and i==temp_lock[2]:
                    ans+=1
                    break
print(ans)

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

int main()
{
	int n, ke, kata[4] = {0};

	while (scanf("%d,%s", &n, &ke) != EOF){
		if (ke == 'A') kata[0]++;
		else if (ke == 'B') kata[1]++;
		else if (ke == 'O') kata[3]++;
		else kata[2]++;
	}
	for (int i = 0; i < 4; i++){
		cout << kata[i] << endl;
	}
	return (0);
}

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

const ll mod=1e9+7;
ll mu(ll a,ll b){
  return (ll)a*b%mod;
}
ll ad(ll a,ll b){
  if((a+=b)>=mod)a%=mod;
  return a;
}
ll pw(ll a,ll b,ll c=1LL){
  for(;b;b>>=1,a=mu(a,a))if(b&1)c=mu(c,a);
  return c;
}
ll dv(ll a,ll b){
  return mu(a,pw(b,mod-2));
}

void comb(ll *c, ll n){
  c[0] = 1;
  rep1(i,n){
    c[i] = mu(c[i - 1], mu(n + 1 - i, dv(1,i)));   
  }

}

int main() {
  ll n,a,b;
  cin >> n >> a >> b;
  // nCk を計算 comb()で初期化、計算やってくれる。

  ll ans = pw(2,n) - 1;
  ll la,lb;
  ll ua,ub;
  la = lb = ua = ub=1;
  rep1(i,a){
    la = mu(la,i);
    ua = mu(ua,(n+1-i));
  }
  rep1(i,b){
    lb = mu(lb,i);
    ub = mu(ub,(n+1-i));
  }

  ans = (ans - dv(ua,la) - dv(ub,lb) +mod + mod + mod)%mod;
   cout << ans << endl;

  return 0;

}


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

int d, g, p[11], c[11];
int ans = 1e9;

void dfs(string s)
{
    if (s.size() == d)
    {
        int score = 0, cnt = 0;
        rep(i, d)
        {
            if (s[i] == '1')
            {
                score += p[i] * 100 * (i + 1) + c[i];
                cnt += p[i];
            }
            if (score >= g)
            {
                ans = min(ans, cnt);
                break;
            }
        }
        per(j, d)
        {
            if (s[j] == '1' || score >= g)
                continue;
            rep(k, p[j])
            {
                score += (j + 1) * 100;
                cnt++;
                if (score >= g)
                {
                    ans = min(ans, cnt);
                    break;
                }
            }
        }
        return;
    }
    dfs(s + "0");
    dfs(s + "1");
}

void solve()
{
    cin >> d >> g;
    rep(i, d) cin >> p[i] >> c[i];
    dfs("");
    cout << ans << endl;
}

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

Measured memory_bytes: 3648
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder.ABC0
{
    class Program
    {
        static void Main ()
        {
            var n = Console.ReadLine ();
            if (n[0].Equals (n[1]) && n[1].Equals (n[2]) || n[1].Equals (n[2]) && n[2].Equals (n[3]))
            {
                Console.WriteLine ("Yes");
            }
            else Console.WriteLine ("No");
        }
    }
}

Measured memory_bytes: 11092
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)

from sys import stdin
from collections import Counter


for line in stdin:
    L = sorted([int(s) for s in line.split(',')])
    cnt = Counter(L)
    length, num = len(cnt), cnt.most_common(1)[0][1]
    if length == 4 and num == 2:
        print('one pair')
    elif length == 3 and num == 2:
        print('two pair')
    elif length == 3 and num == 3:
        print('three card')
    elif length == 2 and num == 3:
        print('full house')
    elif length == 2 and num == 4:
        print('four card')
    elif L[0] == L[1]-1 == L[2]-2 == L[3]-3 == L[4]-4:
        print('straight')
    elif L[0] == 1 and L[1]-1 == L[2]-2 == L[3]-3 == L[4]-4:
        print('straight')
    else:
        print('null')

Measured memory_bytes: 4684
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

int N;
string S;

vector<int> check(int s0, int s1){
    int P[N];
    fill(P, P+N, -1);
    bool fl = true;
    P[0] = s0;
    P[1] = s1;

    vector<int> ret;

    // 0:S, 1:W
    for(int i=0; i<N; i++){
        int b = (N+i-1)%N;
        int a = (i+1)%N;
        if(P[b] == -1) swap(a, b);

        if(P[a] != -1 && P[b] != -1){
            if(S[i] == 'o' && P[i] == 0 && P[b] != P[a]) fl = false;
            if(S[i] == 'o' && P[i] == 1 && P[b] == P[a]) fl = false;
            if(S[i] == 'x' && P[i] == 0 && P[b] == P[a]) fl = false;
            if(S[i] == 'x' && P[i] == 1 && P[b] != P[a]) fl = false;
        }
        if(!fl) break;

        if(S[i] == 'o' && P[i] == 0){
            P[a] = P[b];
        }
        if(S[i] == 'o' && P[i] == 1){
            P[a] = !P[b];
        }
        if(S[i] == 'x' && P[i] == 0){
            P[a] = !P[b];
        }
        if(S[i] == 'x' && P[i] == 1){
            P[a] = P[b];
        }
        ret.push_back(P[i]);
    }

    vector<int> emp;
    if(!fl) return emp;
    else return ret;
}

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

    vector<int> ans;
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++){
            vector<int> t = check(i, j);
            if(!t.empty()){
                ans = t;
            }
        }
    }

    if(ans.empty()){
        cout << -1 << endl;
        return 0;
    }

    for(int i=0; i<N; i++){
        if(ans[i] == 0) cout << "S";
        else cout << "W";
    }
    cout << endl;

    return 0;
}


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

const int N = 200002;

int a[N], p[N], s[N];

int main() {
        ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int n; cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) p[i] = max(p[i - 1], a[i]);
        for(int i = n; i >= 1; i--) s[i] = max(s[i + 1], a[i]);
        for(int i = 1; i <= n; i++) cout << max(p[i - 1], s[i + 1]) << endl;

}


Measured memory_bytes: 3968
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Text;
 
public class Program
{
    public void Proc() {
        Reader.IsDebug = false;
        long inputCount = int.Parse(Reader.ReadLine());
        this.Items = Reader.GetLongs();
        long sum = this.Items.Sum();
        long num = inputCount*(inputCount+1)/2;
 
        if(sum%num!=0) {
            Console.WriteLine("NO");
            return;
        }

        bool ans = true;
        for(int i=1; i<Items.Length; i++) {
            if(!IsCorrect(Items[i-1], Items[i], (int)(sum/num))) {
                ans = false;
                break;
            }
        }

        Console.WriteLine(ans?"YES":"NO");
    }

    private long[] Items;
 
    private bool IsCorrect(long num1, long num2, int remain) {
        if(remain == 0) {
            return (num1 ==0 && num2 == 0);
        }
        if(num1+remain == num2) {
            return true;
        }
        if(num1+remain > num2) {
            int cnt = this.Adjust(0, remain, num1, num2, remain);
            if(cnt < 0) {
                return false;
            }
            return IsCorrect(num1-(this.Items.Length*cnt), num2-cnt, remain-cnt);
        }
        return false;
    }

    private int Adjust (int min, int max, long num1, long num2, int remain) {
        if(max-min <= 1) {
            if(CanAdjust(min, num1, num2, remain)==0) {
                return min;
            } else if(CanAdjust(max, num1, num2, remain)==0) {
                return max;
            }
            return -1;
        }
        int mid = (max+min)/2;
        long ret = CanAdjust(mid, num1, num2, remain);
        if(ret == 0) {
            return mid;
        }
        if(ret > 0) {
            return Adjust(mid, max, num1, num2, remain);
        } else{
            return Adjust(min, mid, num1, num2, remain);
        }
    }

    private long CanAdjust(int count, long num1, long num2, int remain) {
        long tmp1 = num1 - (count*this.Items.Length);
        long tmp2 = num2 - (count);
        if(tmp1 < 0 || tmp2 < 0) {
            return -1;
        }
        return (tmp1 + (remain-count))-tmp2;
    }
 
    public class Reader {
        public static bool IsDebug = true;
 
        public static long[] GetLongs(char delimiter) {
            string inpt = Reader.ReadLine();
            return inpt.Split(delimiter).Select(a=>long.Parse(a)).ToArray();
        }
 
        public static long[] GetLongs() {
            return GetLongs(' ');
        }
        private static System.IO.StringReader SReader;
        private static string InitText = @"


4
1 2 3 1

";
        public static string ReadLine() {
            if(IsDebug) {
                if(SReader == null) {
                    SReader = new System.IO.StringReader(InitText.Trim());
                }
                return SReader.ReadLine();
            } else {
                return Console.ReadLine();
            }
        }
    }
    public static void Main(string[] args)
    {
        Program prg = new Program();
        prg.Proc();
    }
}


Measured memory_bytes: 14552
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
int main(void){
		int a;
		int b;
		int c;
		int d;
		int score;

		scanf("%d",&a);

		b = a/500;

		c = a%500;
		d = c/5;
		score = b*1000 + d*5;

		printf("%d\n",score);


		return 0;
}

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

struct Problem {

	void Solve() {
		UL H, W; cin >> H >> W;
		UL N; cin >> N;
		vector<pair<UL, UL>> P(N);
		rep(i, N) cin >> P[i].first >> P[i].second;
		sort(P.begin(), P.end());
		UL ans = H;
		UL by = 0;
		rep(i, N) {
			if (P[i].first == P[i].second + by) by++;
			if (P[i].first > P[i].second + by) {
				cout << P[i].first - 1 << endl;
				return;
			}
		}
		cout << ans << endl;
	}


	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ちゃんと考えてわかって実装 */

int main(void){
    int k, x;
    cin >> k >> x;
    if(500*k >= x) cout << "Yes";
    else cout << "No";
    return 0;
}

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

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

  int l[n];

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

  int ans =0;
  int count=0;

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

      ans++;
      count += l[i];

      if(count + l[i+1] > x){
          break;
      }
  }

  cout << ans +1 << endl;

  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x = 0;
  int n;
  string s;
  
  cin >> n >> s;
  
  int max = x;
  
  for (char c : s) {
    if (c == 'I')
      x++;
    else
      x--;
    
    if (max < x)
      max = x;
  }
  
  cout << max;
  
}

Measured memory_bytes: 3548
#include<bits/stdc++.h>							
typedef long long ll;
#define pb push_back
#define mod 1000000007ll
const ll maxn = 9e18;
using namespace std;
const ll maxsize = 100000009;



void solve() {
	int n;
	ll cnt = 1;
	cin >> n;
	int arr[n];
	int m_value = 1e9;
	for(int i = 0; i < n; ++i) {
		cin >> arr[i];
		if(!i) continue;
		m_value = min(m_value, arr[i - 1]);
		if(arr[i] <= m_value) cnt++;
		}
		cout << cnt << endl;
}


int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout.precision(35);
	solve();
	return 0;
}
 
 
 


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

int main()
{
  int num; //sum取得のために使う
  int X; //割るためにnumを移しておく
  int dig;
  int sum = 0;

  cin >> num;
  X = num;
  while(num)
  {
    dig = num % 10;
    sum += dig;
    num = num / 10;
  }

  if(X % sum == 0)
  cout << "Yes" << endl;
  else
  cout << "No" << endl;

  return 0;
}


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

void Main(){
  int N;
  cin >> N;
  vector<int> vec(N);
  for(auto& v : vec){
    cin >> v;
  }
  sort(vec.begin(), vec.end(), greater<int>());

  int alice = 0;
  int bob = 0;
  bool aliceTurn = true;
  for(auto& v : vec){
    if(aliceTurn){
      alice += v;
      aliceTurn = false;
    }
    else{
      bob += v;
      aliceTurn = true;
    }
  }

  int res = alice - bob;
  cout << res << endl;
}

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner scn=new Scanner(System.in);
        int n=scn.nextInt();
        int money=scn.nextInt();
        money=money/1000;
        int answer = 0;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n-i;j++){
                int k=n-i-j;
                if(k<0) break;
                if(money==i*10+j*5+k*1&&i+j+k==n){
                    System.out.println(i+" "+j+" "+k);
                     answer++;
                     break;
                }
            }
          	if(answer>0) break;
        }
      	if(answer==0) System.out.println("-1 -1 -1");
    }
}

Measured memory_bytes: 24916
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=300050;
const ll MOD=998244353;
ll s[maxn<<2],s2[maxn<<2],val[maxn];
int laz[maxn<<2];
int n,q;

void pushup(int x){
	s[x]=(s[x<<1]+s[x<<1|1])%MOD;
}
void pushup2(int x){
	s2[x]=(s2[x<<1]+s2[x<<1|1])%MOD;
}
void pushdown2(int x){
	if(laz[x]){
		s2[x<<1]=s[x<<1]*laz[x]%MOD;
		s2[x<<1|1]=s[x<<1|1]*laz[x]%MOD;
		laz[x<<1]=laz[x];laz[x<<1|1]=laz[x];
		laz[x]=0;
	}
}
void build(int x,int l,int r){
	if(l==r){
		s[x]=s2[x]=val[l];return;	
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	pushup(x);pushup2(x);
}
void update(int x,int l,int r,int L,int R,int d){
	if(L<=l&&r<=R){
		s2[x]=s[x]*d%MOD;
		laz[x]=d;return;
	}
	int mid=(l+r)>>1;
	pushdown2(x);
	if(mid>=L)	update(x<<1,l,mid,L,R,d);
	if(mid<R)	update(x<<1|1,mid+1,r,L,R,d);
	pushup2(x);
}
void solve(){
	scanf("%d %d",&n,&q);
	ll now=1;
	for(int i=n;i>=1;i--){
		val[i]=now;now=now*10%MOD;
	}
	build(1,1,n);
	while(q--){
		int l,r,d;
		scanf("%d %d %d",&l,&r,&d);
		update(1,1,n,l,r,d);
		printf("%lld\n",s2[1]);
	}
}
int main(){
	solve();
	return 0;
}

Measured memory_bytes: 14160
/*
    NO 
        TIME 
            TO 
                DIE
                    --007
                            */
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <complex>
//#include <boost/functional/hash.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// define x, y as real(), imag()


template<class T>
istream& operator>> (istream& is, complex<T>& p) {
  T value;
  is >> value;
  p.real(value);
  is >> value;
  p.imag(value);
  return is;
}
#define M_PI 3.14159265358979323846
typedef long long int lli;
lli mod=1e9+9ll;
#define OS //single input use oeis
lli INF=9223372036854775807;
lli eps=1e-8;
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define sqr(x) (x) * (x)
#define bip(n) __builtin_popcountll(n)//no of ones bit in binary!!
#define bictz(n) __builtin_ctzll(n)//no of trailing zeroes in binary!!
#define biclz(n) __builtin_clzll(n)//no of leading zeroes in binary!!
#define bffs(n) __builtin_ffsll(n)//index of first one bit!!
typedef pair<lli,lli> ll;
#define mem1(a,x) fill(&a[0], &a[0] + sizeof(a) / sizeof(a[0]), x)
#define mem2(a,x) fill(&a[0][0], &a[0][0] +sizeof(a)/sizeof(a[0][0]),x)
#define mem3(a,x) fill(&a[0][0][0], &a[0][0][0] +sizeof(a)/sizeof(a[0][0][0]),x)
#define fi1 ifstream fin("input.txt")
#define of1 ofstream fout("output.txt")
int fmx(int x, int y) { return (((y-x)>>(31))&(x^y))^y; }
int fmi(int x, int y) { return (((y-x)>>(31))&(x^y))^x; }
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ost;
lli n,z,k,x,m,d,y,q,b,c,s,t;
const double pi=3.14159265358979323846;
lli me(lli a,lli b)
{
    // cout<<mod<<"\n";
    lli res=1;
    while(b)
    {
        if(b&1)
        res=(res%mod*a%mod)%mod;
        a=a*a;
        a%=mod;
        b=b>>1;
    }
    return res;
}
lli mI(lli a)
{
    return (me(a,mod-2)%mod+mod)%mod;
}
vector<lli> v[1005];
lli mk[1005][1005];
lli vis[1005];
lli val=-1;
void bfs()
{
    queue<ll> q;
    q.push({s,0});
    while(!q.empty())
    {
        ll no=q.front();
        q.pop();
        if(vis[no.first])
        continue;
        vis[no.first]=1;
        if(no.first==t)
        {
            val=no.second;
            break;
        }
        for(auto &j: v[no.first])
        {
            q.push({j,no.second+1});
        }
    }
}
int main()
{
   string s,t;
   cin>>s>>t;
   t.pop_back();
   if(s==t)
   cout<<"Yes";
   else
   cout<<"No";
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(long long i=a; i<b; i+=1)
#define repr(i,a,b) for(long long i=a; i<=b; i+=1)
#define vec vector<ll>
#define map map<string,int>
#define repa(p,A) for(auto p:A)
#define pb push_back
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
const int INF =-1;

using namespace std;
int main() {
  ll H,W;
  cin>>H>>W;
  vector<vector<char>>A(H,vector<char>(W));
  rep(i,0,H) {
    rep(j,0,W) {
      cin>>A[i][j];
    }
  }
  
  

  
  vec B(H*W);
  //予選決勝法のため、各スタート地点の最長ルートをBに保存
  rep(i,0,H*W) {
    vector<ll> dist(H*W,INF);
    queue<int> q;
    auto push =[&](int v, int d) {
      if(dist[v]!=INF) return;
      dist[v]=d;
      q.push(v);
    };
    if(A[i%H][i/H]=='.') {
      push(i,0);
      while(!q.empty()) {
        int v=q.front(); q.pop();
        int d=dist[v];
        if(v/H+1 < W) {
          if(A[v%H][v/H+1]=='.') push(v+H,d+1);
        }
        if(v/H-1 >=0) {
          if(A[v%H][v/H-1]=='.') push(v-H,d+1);
       }
        if(v%H+1 < H) { 
          if(A[v%H+1][v/H]=='.') push(v+1,d+1);
       }
        if(v%H-1 >= 0) {
          if(A[v%H-1][v/H]=='.') push(v-1,d+1);
        }
      }
      sort(dist);
      reverse(dist);
      B[i]=dist[0];
    }
    
  }
  sort(B);
  reverse(B);
  cout<<B[0]<<endl; 
    
  
    
}

Measured memory_bytes: 256