akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

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

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

int main() {
  int N, sum = 0;
  cin >> N;
  vector<int> a(N);
  for(int i = 0; i < N; i++){
    cin >> a.at(i);
    int T = 1;
    for(int j =0; j < i; j++){
      if(a.at(i) == a.at(j))
        T *= 0;
      else
        T *= 1;
    }
    sum += T;
  }
  cout << sum << endl;
}

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

using namespace std;

typedef long long int ll;

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; }

typedef pair<int,int> pair;

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main(){
    ll x; cin >> x;

    ll n=2;
    priority_queue<int> p;
    vector<int> q;
    p.push(n);
    q.emplace_back(n);
    bool fg=true;

    while(x>p.top()){
        n++;
        if(IsPrime(n)){
            p.push(n);
        }
    }

    cout << p.top() << endl;
        
}

Measured memory_bytes: 384
#include<stdio.h>
#include<stdlib.h>
//#include<math.h>

int main(void){
     
     int i,j;
     int A,B,C;
    // int A[100002];
     int sum = 0;
     int max;

     scanf("%d %d %d",&A, &B, &C);

   if(A+B < C)printf("No\n");
   else printf("Yes\n");
   
  
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using lint = long;
using llint = long long;
using namespace std;

class Hash {
  public:
    Hash() : T{make_unique<string[]>(MOD)} {}
    bool find(string s);
    bool insert(string s);

  private:
    llint MOD = 1046527;
    unique_ptr<string[]> T;
    // hash
    int hash1(int key) { return key % MOD; }
    int hash2(int key) { return 1 + (key % (MOD - 1)); }
    // utility for converting string to key(long long integer)
    int getChar(char ch);
    llint getKey(string s);
};

int Hash::getChar(char ch) {
    switch (ch) {
    case 'A':
        return 1;
    case 'C':
        return 2;
    case 'G':
        return 3;
    case 'T':
        return 4;
    default:
        return 0;
    }
}

llint Hash::getKey(string s) {
    llint sum = 0, p = 1;
    for (size_t i = 0; i < s.size(); ++i) {
        sum += p * getChar(s[i]);
        p *= 5;
    }
    return sum;
}

bool Hash::find(string s) {
    llint key = getKey(s);
    for (llint i = 0;; i++) {
        llint hash = (hash1(key) + i * hash2(key)) % MOD;
        if (T[hash] == s)
            return true;
        else if (T[hash].size() == 0)
            return false;
    }
    return false;
}

bool Hash::insert(string s) {
    llint key = getKey(s);
    for (size_t i = 0;; i++) {
        llint hash = (hash1(key) + i * hash2(key)) % MOD;
        if (T[hash] == s)
            return true;
        else if (T[hash].size() == 0) {
            T[hash] = s;
            return false;
        }
    }
    return false;
}

int main() {
    fastIO;

    Hash hash;

    int n;
    cin >> n;

    while (n--) {
        string order, str;
        cin >> order >> str;

        if (order == "insert") {
            hash.insert(str);
        } else {
            if (hash.find(str))
                cout << "yes" << endl;
            else
                cout << "no" << endl;
        }
    }
}



Measured memory_bytes: 23968
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>

#include <cmath>

using namespace std;

int n, T, A, h;

int ans = 1;
double minDiff = 1e10;

int main() {

	cin >> n >> T >> A;

	for (int i = 1; i <= n; ++i)
	{
		cin >> h;

		double diff = fabs(T - A - 0.006 * h);
		if (diff < minDiff) {
			minDiff = diff;
			ans = i;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <vector>

using namespace std;

int a, b;

int gcd(int x, int y) {
    if (x < y) {
        swap(x, y);
    }
    if (x % y == 0) {
        return y;
    }
    return gcd(x % y, y);
}

int main() {
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

Measured memory_bytes: 3084
#include<iostream>
#include<string>
#include<cmath>
#include<array>
#include<algorithm>
//#include<deque>
#include<vector>
//#include<utility>
//#include<set>
#include<map>
//#include<list>
//#include<bitset>
#include<iomanip>

using namespace std;
using LLI = long long int;
LLI N;

//array<int, 8>dir_x = { 0,0,1,1,1,-1,-1,-1 };
//array<int, 8>dir_y = { 1,-1,1,0,-1,1,0,-1 };
//array<int, 4>dir_x2 = { 0,0,1,-1 };
//array<int, 4>dir_y2 = { 1,-1,0,0 };
//char alp[] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };

//class UnionFind {
//public:
//	vector<int>data;
//	UnionFind(int size) :data(size, -1) {};
//	bool unionset(int x, int y) {
//		x = root(x), y = root(y);
//		if (x != y) {
//			if (data[y] < data[x]) {
//				swap(x, y);
//			}
//			data[x] += data[y];
//			data[y] = x;
//		}
//		return x != y;
//	}
//	bool findset(int x, int y) {
//		return root(x) == root(y);
//	}
//	int root(int x) {
//		return data[x] < 0 ? x : data[x] = root(data[x]);
//	}
//	int size(int x) {
//		return -data[root(x)];
//	}
//};

LLI gcd(LLI x, LLI y) {
	LLI  r;
	if (x < y) {
		swap(x, y);
	}
	r = x % y;
	while (r != 0) {
		x = y;
		y = r;
		r = x % y;
	}
	return y;
}
LLI lcm(LLI x, LLI y) {
	return x / gcd(x, y) * y;
}

//long nCr(int n, int r) {
//	long ans = 1;
//	for (int i = n; i > n - r; i--) {
//		ans = ans * i;
//	}
//	for (int i = 1; i < r + 1; i++) {
//		ans = ans / i;
//	}
//	return ans;
//}

//const int n_max = 8;
//array<array<bool, n_max>, n_max>graph;
//int dfs(int v,int N,array<bool,n_max>visited) {
//	int ret = 0;
//	bool all_visited = true;
//	for (int i = 0; i < N;i++) {
//		if (visited[i] == false) {
//			all_visited = false;
//		}
//	}	
//	if (all_visited) {
//		return 1;
//	}
//	for (int i = 0; i < N;i++) {
//		if (graph[v][i] == false) {
//			continue;
//		}
//		if (visited[i] == true) {
//			continue;
//		}
//		visited[i] = true;
//		ret += dfs(i,N,visited);
//		visited[i] = false;
//	}
//	return ret;
//}

//vector<vector<int>>sub;
//int dfs(int id) {
//	if (sub[id].size() == 0) {
//		return 1;
//	}
//	int minP = (int)1e9;
//	int maxP = 0;
//	for (int i : sub[id]) {
//		int P = dfs(i);
//		minP = min(minP, P);
//		maxP = max(maxP, P);
//	}
//	return minP + maxP + 1;
//}

//#define debug(x) cerr << #x << " : " << x << endl
//#define debugv(x) cerr << #x << " : "; for(auto i:x) cerr << i << ", "; cerr<<endl

int main(void) {
	LLI N,sum = 0;
	bool res = false;
	cin >> N;
	vector<pair<LLI, LLI>>vec(N);
	for (int i = 0; i < N;i++) {
		cin >> vec[i].second >> vec[i].first;
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < N;i++) {
		sum += vec[i].second;
		if (sum > vec[i].first) {
			res = true;
			break;
		}
	}
	if (res) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1ll << 50;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
void Yes(bool flag = true) {
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
void No(bool flag = true) {
    Yes(!flag);
}
void YES(bool flag = true) {
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
void NO(bool flag = true) {
    YES(!flag);
}
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define vi vector<int>
//#define P pair<int, int>
//#define V vector<int>
//#define S set<int>
#define itn int
bool dbg = false;

int N;
int A[303030];
int SUM[303030];

int cnt[303030];

void solve() {
    FOR(N)
    cnt[A[i]]++;
    vector<int> V;
    FOR(N + 1)
    if (cnt[i]) {
        V.eb(cnt[i]);
    }
    int M = V.size();
    sort(all(V));
    cerr << M << endl;
    FOR(N + 1) {
        auto it = lb(all(V), i + 1);
        SUM[i + 1] = SUM[i] + (V.end() - it);
    }

    auto check = [&](int k, int x) {
        return SUM[x] >= k * x;
    };

    /*
    FOR(N + 1) {
        cout << i << " : " << SUM[i] << endl;
    }
*/

    FOR(k, 1, N + 1) {
        int ok = 0;
        int ng = N + 1;
        while (abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (check(k, mid)) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        cout << ok << endl;
    }
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> N;
    FOR(N)
    cin >> A[i];


    solve();
    return 0;
}


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

int main(){
    int n; long long diff;
    cin >> n;
    vector<long long> h(n), dp(n);
    for (int i=0; i<n; i++) cin >> h[i];
    
	dp[0]=0;
    for (int i=1; i<n; i++)
    {
        dp[i] = dp[i-1] + abs(h[i-1]-h[i]);
        if (i>=2){
            diff = dp[i-2] + abs(h[i-2]-h[i]);
            if (dp[i] > diff) dp[i] = diff;
        }
      
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define con continue
#define pb push_back
#define fi first
#define se second
#define fr front()
#define one 1.0
#define inf 1000000000000000000
#define ret return
#define all(vl) vl.begin(),vl.end()
#define sor sort 
#define cl clear
#define m_p make_pair 
#define sz(a) a.size()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef map<ll,ll>::iterator itll;
typedef long double ld;
typedef map<ll,ll> mapll;
typedef map<string,ll> mapstl;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll a,b;
	cin>>a>>b;
	if(a == 1)
	{
		if(b==2)cout<<3;
		else cout<<2;
	}
	else if(a == 2)
	{
		if(b == 1)cout<<3;
		else cout<<1;
	}
	else
	{
		if(b == 1)cout<<2;
		else cout<<1;
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <stdio.h>
#include <cmath>
#include <string.h>
#include <vector>

#define ll long long
using namespace std;

int main()
{
    //freopen("C:\\Users\\23733\\Desktop\\in.txt","r",stdin);
    char str[3][3];
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            cin >> str[i][j];
    cout << str[0][0] << str[1][1] << str[2][2] << endl;
    return 0;
}


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

int main() {
int N,K,i,j;
cin>>N>>K;
int ans=0;
for(i=0 ; i<N ; i++){
cin>>j;
if(K<j){
ans+=(j-K)*2;
}
else{
ans+=min(K-j ,j)*2;
}
}
cout<<ans<<endl;
}



Measured memory_bytes: 256
import java.util.Scanner;

/**
 *
 * @author k16075kk
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int[] alphabet = new int[26];

        do {
            String s = input.nextLine();
            for (char c : s.toCharArray()) {
                if ((c < 'A' || 'Z' < c) && (c < 'a' || 'z' < c)) {
                    continue;
                }
                alphabet[Character.toLowerCase(c) - 'a']++;
            }
        } while (input.hasNext());

        for (char c = 'a'; c <= 'z'; c++) {
            System.out.println(c + " : " + alphabet[c - 'a']);
        }
    }
}





Measured memory_bytes: 26064
s=input()
a=[]
su=0
k=0
def wa(x):
  j=0
  t=0
  for i in range(x):
    j+=1
    t+=j
  return t
def unkosumaho(x):
  b=0
  c=0
  for i in range(len(x)):
    if x[i]=='<':
      b+=1
    else:
      c+=1
  return wa(max(b,c))+wa(min(b,c)-1)
for i in range(len(s)-1):
  if s[i]=='>':
    if s[i+1]=='<':
      a.append(s[k:i+1])
      k=i+1
  if i==len(s)-2:
      a.append(s[k:])
for i in a:
  su+=unkosumaho(i)
if (len(s))==1:
  print(1)
else:
  print(su)

Measured memory_bytes: 12192
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long n;
	cin>>n;
	long a[n],b[n];
	for(int i=0;i<n;i++)
	cin>>a[i];
	b[0]=0;
	b[1]=abs(a[1]-a[0]);
	for(int i=2;i<n;i++)
	{
		b[i]=((b[i-1]+abs(a[i-1]-a[i]))<(b[i-2]+abs(a[i-2]-a[i])))?(b[i-1]+abs(a[i-1]-a[i])):(b[i-2]+abs(a[i-2]-a[i]));
	}
	cout<<b[n-1];
	return 0;
}

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

#define reps(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   reps(i,0,n)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define PI (acos(-1))

int sum[100000];
//sum[i] = スタートとなりうるマス（iをDで割った余りのマス）からiに来るまでのコスト合計）
int H,W,D;
int A[310][310];
map <int,pair<int,int> > m;//A[i][j]が与えられた時i,jにアクセスする

int rec(int n){
  //cout << "rec" << " " << n << " " << D << endl;
  if(n <= D){
    return sum[n] = 0;
  }else{
    if(sum[n] != 0){//訪問済み
      return sum[n];
    }
    auto p = m[n];
    int ny = p.first;
    int nx = p.second;
    auto pmae = m[n-D];
    int nymae = pmae.first;
    int nxmae = pmae.second;
    int res=0;
    return sum[n] = rec(n-D) + abs(ny-nymae) + abs(nx-nxmae);
    return 1;
  }
}

int main(){
  cin >> H >> W >> D;
  //cout << D << endl;
  rep(i,H){
    rep(j,W){
      cin >> A[i][j];
      m[A[i][j]] = make_pair(i,j);
    }
  }

  rep(i,H){
    rep(j,W){
      rec(A[i][j]);
      //cout << A[i][j] << " " <<  tmp << endl;
    }
  }

  int Q;
  cin >> Q;
  rep(i,Q){
    int L,R;
    cin >> L >> R;
    cout << sum[R]-sum[L] << endl;
  }
}

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

typedef long long ll;

const ll mod = 1000*1000*1000+7;

vector<ll> fact;
int N, K;
vector<int> P;

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4*N, 0);
    }
    void upd(int idx, int val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = val;
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = tree[2*n] + tree[2*n + 1];
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 0;
        if(a <= l && r <= b) return tree[n];
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return L + R;
    }
} bit, sub;

int main() {
    fact.resize(500010);
    fact[0] = 1;
    for(int i = 1; i < 500010; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }

    scanf("%d", &N);
    K = 0;
    P.resize(N);
    sub.init();
    for(int i = 0; i < N; i++) {
        scanf("%d", &P[i]);
        P[i]--;
        if(P[i] == -1) K++;
        sub.upd(i, 1, 0, N - 1, 1);
    }

    ll sum = 1LL * N * (N - 1) / 2;
    for(int i = 0; i < N; i++) {
        if(P[i] != -1) sum -= P[i], sub.upd(P[i], 0, 0, N - 1, 1);
    }
    sum = (sum % mod + mod) % mod;

    bit.init();
    ll ans = 0;
    ll tmp = 0;
    int cnt = 0;
    for(int i = 0; i < N; i++) {
        if(P[i] == -1) {
            ll a = sum * fact[K - 1] % mod;
            ll b = tmp * fact[K - 1] % mod;
            ll c = K < 2? 0 : (1LL * K * (K - 1) / 2 % mod) * fact[K - 2] % mod * cnt % mod;

            ans += (a - b - c) * fact[N - i - 1] % mod, ans = (ans % mod + mod) % mod;

            cnt++;
        }
        else {
            bit.upd(P[i], 1, 0, N - 1, 1);
            tmp += sub.quer(P[i] + 1, N - 1, 0, N - 1, 1);
            tmp %= mod;

            ll a = fact[K] * P[i] % mod;
            ll b = fact[K] * bit.quer(0, P[i] - 1, 0, N - 1, 1) % mod;
            ll c = K == 0? 0 : fact[K - 1] * sub.quer(0, P[i] - 1, 0, N - 1, 1) % mod * cnt % mod;

            ans += (a - b - c) * fact[N - 1 - i] % mod, ans = (ans % mod + mod) % mod;
        }
    }
    cout << (ans + fact[K]) % mod;
}


Measured memory_bytes: 21760
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
#include<map>
#include<set>
using namespace std;

int main() {
    int n, k, h, m = 1000000000;
    cin >> n >> k;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        cin >> h;
        v.push_back(h);
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n - k+1; i++) {
        m = min(m, v[i + k - 1] - v[i]);
    }
    cout << m << endl;
}

  

Measured memory_bytes: 1020
#include <iostream>
#include <algorithm>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int BN = 210000;
struct BIT {
	int bit[252521];
	void add(int a, int w) {
		for (int x = a; x <= BN; x += x & -x) bit[x] += w;
	}
	int sum(int a) {
		int ret = 0;
		for (int x = a; x > 0; x -= x & -x) ret += bit[x];
		return ret;
	}
	void init() {
		for (int i = 0; i <= BN; i++) bit[i] = 0;
	}
};	//array[N + 1 + i] = 値iの個数

int n;
int a[100000];
int b[100000];
int rb[100001];
BIT seg;

bool check(int X) {
	int i;
	rep(i, n) {
		if (a[i] >= X) b[i] = 1;
		else b[i] = -1;
	}
	rep(i, n + 1) rb[i] = 0;
	rep(i, n) rb[i + 1] += rb[i] + b[i];
	
	//0 <= l < r <= nかつrb[l] <= rb[r]を満たす(l, r)の組み合わせ数
	seg.init();
	int ret = 0;
	for (i = n; i >= 0; i--) {
		//rb[i]以上の値の個数 == (n - i) - rb[i]未満の値の個数
		ret += n - i - seg.sum(n + rb[i]);
		//更新
		seg.add(n + rb[i] + 1, 1);
	}
	
	int minus = n * (n + 1) / 2 - ret;
	//cout << X << " " << minus << " " << ret << endl;
	return minus <= ret;
}

signed main() {
	int i;
	
	cin >> n;
	rep(i, n) cin >> a[i];
	
	check(30);
	
	int st = 0, ed = 1000000007, mid;	//oooxxx, [st, ed)
	while (ed - st >= 2) {
		mid = (st + ed) / 2;
		if (check(mid)) st = mid;	//答えがmid以上か？
		else ed = mid;
	}
	cout << st << endl;
	return 0;
}

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

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

using Graph = vector<vector<int>>;

ll calc(ll a, ll b, ll p){//aのb乗をpで割った余り
  if(b == 0) return 1;

  else if(b%2 == 0){
    ll d = calc(a,b/2,p);
    return (d*d)%p;
  }
  else if(b%2 == 1){
    return (a * calc(a,b-1,p))%p;
  }
}

typedef pair<int,int> P;

bool is_prime(int n){//nが素数であるかどうか判定 iで割り切れると素数でない
    if(n == 1) return false;//1は例外
    for(int i = 2;i*i <= n;i++){
        if(n%i == 0) return false;
    }
    
    return true;
}
int factorial(int a){
  int res = 1;
  while(a){
    res *= a;
    a--;
  }
  return res;
}

int main(){
  ll A,B,C;
  cin >> A >> B >> C;
  cout << min(A+B+1,C) + B << endl;
}

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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<string, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

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

    int n, q;
    cin >> n >> q;
    int res = 0;
    queue<P> que;
    for (int i = 0; i < n; i++)
    {
        string name;
        int ti;
        cin >> name >> ti;
        que.push(P(name, ti));
    }
    while (!que.empty())
    {
        string name = que.front().first;
        int ti = que.front().second;
        que.pop();
        if (ti <= q)
        {
            res += ti;
            cout << name << " " << res << endl;
        }
        else
        {
            res += q;
            ti -= q;
            que.push(P(name, ti));
        }
    }
}



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

#define fi first
#define se second
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define pb push_back
#define ll long long

typedef pair<ll, ll> ii;

const int N = 2e5 + 10;
const ll oo = 1e18;

int n;
int a[N];
ll f[N], tmp;
vector<ii> vi;
bool check(ii l1, ii l2, ii l3) {
    return 1ll * (l3.se - l1.se) * (l1.fi - l2.fi) <= 1ll * (l1.fi - l3.fi) * (l2.se - l1.se);
}
void add(ll A, ll B)  {
    vi.pb(ii(A, B));
    int cnt = vi.size();
    while(vi.size() >= 3 && check(vi[cnt - 3], vi[cnt - 2], vi[cnt - 1]))   {
        auto cur = vi.back(); vi.pop_back(); vi.pop_back();
        vi.pb(cur); cnt -= 1;
    }
}
ll get(ll val)  {
    int l = 0, r = vi.size() - 1;
    while(r > l)    {
        int mid = (l + r) / 2;
        if(mid == vi.size() - 1 || 1.00 * val <= 1.00 * (vi[mid + 1].se - vi[mid].se) / (double)(vi[mid].fi - vi[mid + 1].fi))
            r = mid;
        else l = mid + 1;
    }
    return 1ll * (vi[l].fi * val + vi[l].se);
}
signed main()
{
    //freopen("test.inp", "r", stdin);
    scanf("%d%lld", &n, &tmp);
    FOR(i, 1, n) scanf("%d", &a[i]);
    add(-2ll * a[1], 1ll * a[1] * a[1]);
    FOR(i, 2, n)    {
        f[i] = 1ll * a[i] * a[i] + get(a[i]) + tmp;
        add(-2ll * a[i], f[i] + 1ll * a[i] * a[i]);
    }
    printf("%lld", f[n]);
}


Measured memory_bytes: 8560
s = input()
n = len(s)

if s[0] != "A" or s[1].isupper() or s[n-1] == "C" or s[2:].count("C") != 1:
    print("WA")
    exit()

for i in range(n):
    if s[i] == "C":
        s1 = s[1:i] + s[i+1:]

if s1.islower():
    print("AC")
else:
    print("WA")
    exit()

Measured memory_bytes: 3060
#include "bits/stdc++.h"
#define MOD 1000000007
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

int N;
std::string S1, S2;
LL ans = 1;

int main()
{
	in >> N >> S1 >> S2;

	rep(i, N)
	{
		// Begin
		if (i == 0)
		{
			// Pattern 1 or 3
			if (S1[i] == S2[i]) { ans *= 3; }

			// Pattern 2
			else
			{
				ans *= (3 * 2);
				++i;
			}
		}

		// Not begin
		else
		{
			// Pattern 1
			if (S1[i] == S2[i])
			{
				if (S1[i - 1] == S2[i - 1]) { ans *= 2; }
				else { ans *= 1; }
			}

			// Pattern 2 or 3
			else
			{
				if (S1[i - 1] == S2[i - 1]) { ans *= (2 * 1); }
				else { ans *= 3; }
				++i;
			}
		}

		ans %= MOD;
	}

	out << ans << std::endl;
	return 0;
}

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

int main(){
    int n,m,x;
    cin >> n >> m >> x;
    int a[n] = {};
    int t;
    for(int i=0;i<m;i++){
        cin >> t;
        a[t] = 1;
    }
    int left=0,right=0;
    for(int i=1;i<n;i++){
        if(i < x){
            left += a[i];
        }
        if(i > x){
            right += a[i];
        }
    }
    cout << min(left,right) << endl;    
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tmp;
		int i =0;
		while((tmp = sc.nextInt()) != 0) {
			i++;
			System.out.printf("Case %d: %d\n",i,tmp);
		}

	}
}



Measured memory_bytes: 65160
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

A, B = MAP()
A -= 1
n = len(str(bin(B)))-2
a = [0]*n
b = [0]*n

def cnt_bit(cnt, N):
	for i in range(n):
		p = N//(2**(i+1)) * 2**i
		q = N%(2**(i+1))
		if 2**i <= q:
			p += min(2**i, q-(2**i-1))
		cnt[i] = p

cnt_bit(a, A)
cnt_bit(b, B)

ans = 0
for i in range(n):
	if (b[i]-a[i])%2:
		ans += 2**i

print(ans)

Measured memory_bytes: 10444
#include <iostream>
using namespace std;
int main()
{
    int s[10001];
    int n,q,i,j,c=0,t;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>s[i];
    cin>>q;
    for(i=0;i<q;i++)
    {
        cin>>t;
        j = 0;
        s[n] = t;
        while(s[j]!=t)
            j++;
        if(j!=n)
            c++;
    }
    cout<<c<<endl;
    return 0;
}

Measured memory_bytes: 3116
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    now = inf
    ans = 0
    for a in A:
        if a<=now:
            ans+=1
            now = a
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 72816
import java.util.*;
public class Main{
	public static void main(String args[]){

		Scanner ob = new Scanner(System.in);
		int X = ob.nextInt();
		int kyu;

		if ((X >= 400) && (X <= 599)) {
			kyu = 8;
		}
		else if((X >= 600) && (X <= 799)){
			kyu = 7;
		}
		else if((X >= 800) && (X <= 999)){
			kyu = 6;
		}
		else if((X >= 1000) && (X <= 1199)){
			kyu = 5;
		}
		else if((X >= 1200) && (X <= 1399)){
			kyu = 4;
		}
		else if((X >= 1400) && (X <= 1599)){
			kyu = 3;
		}
		else if((X >= 1600) && (X <= 1799)){
			kyu = 2;
		}
		else{
			kyu = 1;
		}

		System.out.println(kyu);
	}
}

Measured memory_bytes: 35668
#include <bits/stdc++.h>
#include <math.h>
#include <vector>
#include <queue>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep_1 (i,j,n) for(int i=j;i<n;i++)
typedef long long ll;
typedef long l;
const ll l_INF = 1010101010101010;
const int INF = 1010101010;
const int dx[] = {-1,0,1,0,-1,-1,1,1};
const int dy[] = {0,-1,0,1,1,-1,1,-1};

int main(){
  int n,w; cin>>n>>w;
  int value[n],weight[n];
  rep(i,n) cin>>value[i]>>weight[i];
  int dp[101010]; //dp[i]:重さi以下の時の最小値
  dp[0]=0;
  rep(i,w){
    dp[i+1]=dp[i];
    rep(j,n){
      if(i+1-weight[j]>=0) dp[i+1]=max(dp[i+1],dp[i+1-weight[j]]+value[j]);
    }
  }
  /*rep(i,w){
    cout<<dp[i]<<endl;
  }*/
  cout<<dp[w]<<endl;
}



Measured memory_bytes: 3168
import sys
read = sys.stdin.buffer.read
#input = sys.stdin.readline
#input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')
import math


def main():
	
	k=II()
	
	ans=0
	
	li=[[0]*(k+1) for i in range(k+1)]
	
	for a in range(1,k+1):
		for b in range(1,k+1):
			for c in range(1,k+1):
				d=math.gcd(a,b)
				ans+=math.gcd(d,c)
				
	
	print(ans)





	
if __name__ == "__main__":
	main()


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

using namespace std;

int main() {
    int N;
    int D;
    vector<vector<int>> mats;

    cin >> N >> D;
    mats.resize(N);
    for (size_t idx = 0; idx < N; ++idx) {
        mats[idx].resize(D);
    }
    for (size_t idx = 0; idx < N; ++idx) {
        for (size_t jdx = 0; jdx < D; ++jdx) {
            cin >> mats[idx][jdx];
        }
    }

    int ct = 0;

    for (size_t idx = 0; idx < N - 1; ++idx) {
        for (size_t jdx = idx + 1; jdx < N; ++jdx) {
            int ires = 0;
            float res = 0.0;
            for (size_t dim = 0; dim < D; ++dim) {
                 float i_d = static_cast<float>(mats[idx][dim]);
                 float j_d = static_cast<float>(mats[jdx][dim]);
                 float dist = (i_d - j_d) * (i_d - j_d);
                 int int_dist = mats[idx][dim] - mats[jdx][dim];
                 int int_dist2 = int_dist * int_dist;
                 res += dist;
                 ires += int_dist2;
            }
            res = sqrt(res);
            // cout << res << endl;
            ires = static_cast<int>(sqrt(ires));
            // cout << ires << endl;
            if (res == ires) {++ct;}
        }
    }

    cout << ct << endl;

    return 0;
}


Measured memory_bytes: 256
def solve(string):
    m = 10**9 + 7
    a, b = 0, 1
    for l in string:
        a, b = ((3 * a + b) % m, 2 * b % m) if l == "1" else (3 * a % m, b)
    return str((a + b) % m)


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


Measured memory_bytes: 3188
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _20170409_AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine(n * n * n);
            Console.Read();
        }
    }
}

Measured memory_bytes: 9172
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';

//INSERT ABOVE HERE
signed solve(){
  Int n;
  cin>>n;
  vector<Int> vs(n),ls(n),rs(n);
  for(Int i=0;i<n;i++) cin>>vs[i]>>ls[i]>>rs[i];

  Int sum=0;
  for(Int i=0;i<n;i++) sum+=min(ls[i],rs[i]);

  vector<Int> dp(n+1,0);
  {
    vector<vector<Int>> G(n+1);
    for(Int i=0;i<n;i++){
      if( (ls[i]<rs[i])) continue;
      G[vs[i]].emplace_back(i);
    }
    using P = pair<Int, Int>;
    set<P> malta;
    Int res=0;
    for(Int i=1;i<=n;i++){
      for(Int k:G[i]){
        res+=ls[k]-rs[k];
        malta.emplace(ls[k]-rs[k],k);
      }
      while((Int)malta.size()>i){
        Int k=malta.begin()->second;
        res-=ls[k]-rs[k];
        malta.erase(malta.begin());
      }
      dp[i]=res;
    }
  }

  vector<Int> pd(n+1,0);
  {
    vector<vector<Int>> G(n+1);
    for(Int i=0;i<n;i++){
      if(!(ls[i]<rs[i])) continue;
      G[vs[i]].emplace_back(i);
    }
    using P = pair<Int, Int>;
    set<P> malta;
    Int res=0;
    for(Int i=n;i>=0;i--){
      for(Int k:G[i]){
        res+=rs[k]-ls[k];
        malta.emplace(rs[k]-ls[k],k);
      }
      while((Int)malta.size()>n-i){
        Int k=malta.begin()->second;
        res-=rs[k]-ls[k];
        malta.erase(malta.begin());
      }
      pd[i]=res;
    }
  }

  cout<<sum+dp[n]+pd[0]<<newl;
  return 0;
}

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

  Int T;
  cin>>T;
  while(T--) solve();

  return 0;
}


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

#ifdef _DEBUG
#define dout cout
#define debug() if (true)
#define dvout(v) vout(v)
#else
#define dout if (false) cout
#define debug() if (false)
#define dvout(v) if(false) vout(v)
#endif

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define all(x) (x).begin(), (x).end()
#define vout(v)           \
	for (auto &i : v)     \
	{                     \
		cout << i << " "; \
	}                     \
	cout << "\n"; //配列出力
#define vec(v, n) vector<int> v(n, 0);
#define vecll(v, n) vector<ll> v(n, 0);
#define vecvec(v,n,m) vector<vector<int>> v(n, vector<int>(m));
#define vin(v)        \
	for (auto &i : v) \
		cin >> i; //配列入力

#define mod (int)(1e9+7)
typedef long long ll;
typedef unsigned long long ull;
#define next asdnext
#define prev asdprev
#define _n "\n"
#define _n2 "\n\n"
#define _t "\t"

//	LLONG_MAX 9.2*1e18	9223372036854775807LL = (2^63)-1
//	INT_MAX 2.1*1e9 2147483647 = (2^31)-1
//	O(1e8) 1.2sec

void Main()
{
	int N;
	cin>>N;
	ll ans1=1,ans2=1,ans3=1;
	rep(i,N){
		ans1=(ans1*10)%mod;
		ans2=(ans2*8)%mod;
		ans3=(ans3*9)%mod;
	}

	dout<<"ans1:"<<ans1<<_t;
	dout<<"ans2:"<<ans2<<_t;
	dout<<"ans3:"<<ans3<<_t;
	ll ans = ans1-(2*ans3)+ans2;
	while(ans<0)ans+=mod;
	cout<<ans<<_n;
}


void Test();
int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << std::fixed << std::setprecision(15);
	Main();
	return 0;
}


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

#define FO(x) {freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout);}
#define fir first
#define sec second
using namespace std;
typedef long long LL;

template <typename T> inline bool cmin(T & a, const T & b) { return a > b ? a = b, 1 : 0;}
template <typename T> inline bool cmax(T & a, const T & b) { return a < b ? a = b, 1 : 0;}
int inp() {
	int x = 0, f = 1;char ch;
	for(ch = getchar(); !isdigit(ch); ch = getchar())
		if(ch == '-') f = -1;
	for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	return x * f;
}
const int MAXN = 201234;
int n, a[MAXN];
int abs(int x) {
	return x < 0 ? -x : x;
}
int main() {
	LL i, j = 0, k = 0, ans = 1e15;
	n = inp();
	for(i = 1; i <= n; i++) a[i] = inp(), j += a[i];
	for(i = 1; i < n; i++){
		k += a[i];
		cmin(ans, abs(j - k - k));
	}
	cout << ans;
	return 0;
}




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

using namespace std;
using ll=long long;
int main(void){
    // Your code here!
    int n,K;
    cin>>n>>K;
    constexpr ll inf=1e15;
    vector<ll> a(n);
    vector<ll> dp(n+4,inf);
    for(auto &b : a)cin>>b;
    dp[0]=0;
    for(int i=0;i<n;++i){
        for(int k=1;k<=K;++k)
            if(i+k<n)dp[i+k] = min(dp[i+k],dp[i]+abs(a[i+k]-a[i]));
    }
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int a,b,c,d,e,f,g,h,i,j;

    long long int ans=0,k=0;
    bool flag=true;
    string s;
    map<char,int>m;
    map<char,int>::iterator it;
    vector<char>v;

    cin>>s>>k;
    i=0;
    j=0;
    while(flag)
    {
        if(s[i] != '1')
        {
            ans= s[i]-'0';
            flag = false;
            i++;
        }
        else
        {
            i++;
        }
    }
    if(i>s.size())
    {
        cout<<"1"<<endl;
    }
    else
    {
        if(k<i)
        {
            cout<<"1"<<endl;
        }
        else
        {
            cout<<ans<<endl;
        }
    }
    return 0;

}




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


int main(){
    int N=0;
    cin >> N;
    long long int sum = 0;
    for(int i=1;i<=N;i++){
        if(i%3!=0&&i%5!=0)  sum+=i;
    }
    // long long int sum = (1+N)*N/2
    // long long int five = (5+(N/5)*5)*(N/5)/2;
    // long long int three = (3+(N/3)*3)*(N/3)/2;
    // long long int fb = (15+(N/15)*15)*(N/15)/2;
    // sum = sum -five -three +fb;
    cout << sum;
    return 0;
}

Measured memory_bytes: 3636
import java.util.Scanner;

/**
 *
 * @author k16075kk
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int[][][] list = new int[4][3][10];
        for (int i = 0; i < a; i++) {
            int b = scanner.nextInt() - 1;
            int c = scanner.nextInt() - 1;
            int d = scanner.nextInt() - 1;
            int e = scanner.nextInt();
            list[b][c][d] += e;
        }

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 10; k++) {
                    System.out.print(" " + list[i][j][k]);
                }
                System.out.println();
            }
            if (i != 3) {
                System.out.println("####################");
            }
        }
    }
}



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

int main() {
  int N ,L;
  cin >> N >> L;
  
  int taste;
  int i;
  if ( L <= 0 &&  L + N - 1 >= 0 ) {
    for ( i=0; i<N; i++ ) {
      taste = taste + L + i;
    }
    cout << taste << endl;
  }
  else if ( L > 0 ) {
    for ( i=0; i<N-1; i++ ) {
      taste = taste + L + i + 1;
    }
    cout << taste << endl;
  }
  else {
    for ( i=0; i<N-1; i++ ) {
      taste = taste + L + i;
    }
    cout << taste << endl;
  }
}


Measured memory_bytes: 256
#include<stdio.h>
int MIN(int a,int b){return a<b?a:b;}
int main(){
  int n,i,b[200010]={};
  char s[200010];
  int m=1e9,w[200010]={};
  scanf("%d %s",&n,s);
  for(i=0;i<n;i++)w[i+1]=w[i]+(s[i  ]=='#'?1:0);
  for(i=n;i  ;i--)b[i-1]=b[i]+(s[i-1]=='.'?1:0);
  //for(i=0;i<=n;i++)printf("%d %d\n",b[i],w[i]);
  for(i=0;i<=n;i++)m=MIN(m,b[i]+w[i]);
  printf("%d\n",m);
  return 0;
}


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

int main() {
	bool ba, bb, bc;
	char x, y;
	ba = true;
	bb = false; bc = false;
	while (scanf("%c,%c", &x, &y) + 1) {
		if ((x == 'A'&&y == 'B') || (x == 'B'&&y == 'A')) { swap(ba, bb); }
		else if ((x == 'A'&&y == 'C') || (x == 'C'&&y == 'A')) { swap(ba, bc); }
		else if ((x == 'B'&&y == 'C') || (x == 'C'&&y == 'B')) { swap(bb, bc); }
	}
	if (ba == true) { cout << 'A' << endl; }
	else if (bb == true) { cout << 'B' << endl; }
	else if (bc == true) { cout << 'C' << endl; }
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef pair<ll,P>  PP;
typedef vector<ll> Vector;
typedef vector<Vector> DVector;
typedef priority_queue<PP, vector<PP>, greater<PP>> PPQueue;

#define fi          first
#define se          second
#define sfi         se.fi
#define sse         se.se
#define pb          push_back
#define INF         1000000000000
#define MOD         1000000007
#define bcnt        __builtin_popcount
#define all(x)      (x).begin(),(x).end()
#define uni(x)      x.erase(unique(all(x)),x.end())
#define ub(x,y)     (upper_bound(all(x),y)-x.begin())
#define lb(x,y)     (lower_bound(all(x),y)-x.begin())
#define rep(i,n)    repl(i,0,n-1)
#define usort(x)    sort(all(x))
#define dsort(x)    sort(all(x),greater<ll>())
#define mkp(x,y)    make_pair(x,y)
#define mmax(x,y)   (x>y?x:y)
#define mmin(x,y)   (x<y?x:y)
#define maxch(x,y)  x=mmax(x,y)
#define minch(x,y)  x=mmin(x,y)
#define exist(x,y)  (find(all(x),y)!=x.end())
#define each(itr,v) for(auto itr:v)
#define repl(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++)

ll f(ll b, ll n){
  if(n < b)return n;
  else return f(b,n/b) + (n % b);
}

int main(){
  cin.sync_with_stdio(false);
  ll n,s;
  cin >> n >> s;
  ll ab = INF;
  if(s < n){
    repl(b,2,sqrt(n))if(s == f(b,n))minch(ab,b);
    for(ll p = sqrt(n); p >= 1; p--){
      if((n - s) >= p || (n - s) % p == 0){
        ll b = (n - s)/p + 1;
        if(s == f(b,n))minch(ab,b);
      }
    }
  }else if(s == n){
    ab = n + 1;
  }
  cout << (ab == INF ? -1 : ab) << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    static final int INF = 100000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int D = sc.nextInt();
        long G = sc.nextLong();
        int[] p = new int[D];
        int[] c = new int[D];
        for (int i = 0; i < D; i++) {
            p[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }
        int min = INF;
        for (int bit = 0; bit < (1 << D); bit++) {
            int score = 0;
            int solve_num = 0;
            for (int i = 0; i < D; i++) {
                if ((bit & (1 << i)) != 0) {
                    score += 100 * (i + 1) * p[i] + c[i];
                    solve_num += p[i];
                }
            }
            if (score < G) {
                loop: for (int i = D - 1; i >= 0; i--) {
                    if ((bit & (1 << i)) == 0) {
                        for (int j = 0; j < p[i] - 1; j++) {
                            score += 100 * (i + 1);
                            solve_num++;
                            if (score >= G) {
                                break loop;
                            }
                        }
                    }
                }
            }
            if (score >= G) {
                min = Math.min(min, solve_num);
            }
        }
        System.out.println(min);
        sc.close();
    }

    
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
  
using namespace std;
  
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
#define forit(it, st) for(auto it : st)
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
  
const int inf = int(1e9);
const int mod = inf + 7;
const int N = 1e6 + 555; // TL MB
const double PI = acos(-1.0);

void solve(){
	int n;
	cin >> n;
	string s, t;
	cin >> s >> t;
	s += t;
	rep(i, n) cout << s[i] << s[i + n];
}
 
int main()
{
    Red;
  	// int T; cin >> T; while(T--)
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
void check(int a[], char r) {
	int  b;
	for (b = 0; b < 13; b++) {
		if (a[b] != b + 1) {
			cout << r << ' ' << b + 1 << endl;
		}
	}
}
int main() {
	int s[13], h[13], c[13], d[13], n, j;
	char x;
	cin >> n;
	for (int i = 0; i < 13; i++) {
		s[i] = 100;
		h[i] = 100;
		c[i] = 100;
		d[i] = 100;
	}
	for (int i = 0; i < n; i++) {
		cin >> x >> j;
		if (x == 'S') {
			s[j - 1] = j;
		}
		if (x == 'H') {
			h[j - 1] = j;
		}
		if (x == 'C') {
			c[j - 1] = j;
		}
		if (x == 'D') {
			d[j - 1] = j;
		}
	}
	check(s,'S');
	check(h,'H');
	check(c,'C');
	check(d,'D');
	return 0;
}

Measured memory_bytes: 3076
import java.util.Scanner;
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 = 6-(A+B);

        System.out.println(C);
      
    }
}

Measured memory_bytes: 21332
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int p[110],q[110];
int main() {
    ll n;
    int l=0,r=0,t=0;
    cin>>n;
    while(n) {
	++t;
	if(n&1) p[++l]=t,n>>=1;
	else q[++r]=t,--n;
    }
    cout<<t+t<<endl;
    for(int i=1;i<=r;i++) cout<<q[i]<<' ';
    while(l)  cout<<p[l--]<<' ';
    while(t) cout<<t--<<' ';
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main() {
	string t;
	cin >> t;
	for (int i = 0; i < t.size(); i++)
	{
		if (t[i] == '?')
		{
			cout << 'D';

		}
		else
		{
			cout << t[i];
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3724