akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int main(void){
	int N,i,j,num[101]={0},temp,cnt=0;
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf("%d",&num[i]);
	}
	for(i=0;i<N;i++){
		for(j=N-1;j>i;j--){
			if(num[j]<num[j-1]){
				temp=num[j];
				num[j]=num[j-1];
				num[j-1]=temp;
				cnt++;
			}
		}
	}
	for(i=0;i<N;i++){
		printf("%d",num[i]);
		if(i!=N-1) printf(" ");
	}
	printf("\n%d\n",cnt);
	return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main() {

   string input;
   cin >> input;

   while(input.compare("0") != 0) {

      int sum = 0;

      stringstream change;

      int max = input.length();

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

         int value = 0;
         change.str("");
         change.clear(stringstream::goodbit);

         change << input[i];
         change >> value;
         sum += value;

      }

      cout << sum << endl;

      cin >> input;

   }

   return 0;

}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
#include <algorithm>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

 
int main() {

    ll x;
    cin >> x;

    for(int i =-1000;i<1000;i++) {
        for(int j = -1000;j<1000;j++) {
            if(pow(i,5) - pow(j,5) == x) {
                cout<<i<<' '<<j<<endl;
                return 0;
            }
        }
    }




 return 0;
}


Measured memory_bytes: 4064
N, H = map(int, input().split())
a = []
b = []
for i in range(N):
    tmp1, tmp2 = map(int, input().split())
    a.append(tmp1)
    b.append(tmp2)

b.sort(reverse=True)
maxOfa = max(a)

ans = 0
while (H > 0):
    if ans < len(b) and b[ans] > maxOfa:
        H -= b[ans]
        ans += 1
    else:
        ans +=(H + maxOfa - 1) // maxOfa
        H = 0

print(ans)


Measured memory_bytes: 11344
def gcd(a,b):
  while b:a,b=b,a%b
  return a
n,k=map(int,input().split())
a=list(map(int,input().split()))
g=a[0]
for i in a[1:]:g=gcd(g,i)
ans="IMPOSSIBLE"
for i in a:
  if k>i:continue
  if abs(k-i)%g==0:ans="POSSIBLE"
print(ans)

Measured memory_bytes: 14252
n, d = (int(i) for i in input().split())
num = list((list(map(int, input().split())) for j in range(n)))
sum = 0
cnt = 0
for k in range(n - 1) :
  for t in range(k + 1, n) :
    for h in range(d) :
      sum += (num[k][h] - num[t][h])**2
    work = sum**(1 / 2)
    temp = work * 10
    temp = temp % 10
    if temp == 0 :
      cnt += 1
    sum = 0
print(cnt)

Measured memory_bytes: 3188
# -*- coding: utf-8 -*-
# 整数の入力

a = input()
# スペース区切りの整数の入力
H,W=a.split(" ")
N=int(H)
M=int(W)
retnum=0
for i in range(N):
    retnum+=i
retnum+=M*(M-1)/2
print(int(retnum))

Measured memory_bytes: 3064
/* 
 * Project: AtCoder Beginners Contest 178 B - Product Max
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/09/13
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <cstdio>
#include <cstdint>
#include <algorithm>
using namespace std;

int64_t a, b, c, d;

void solve() {

    int64_t product = -1000000000000000000;
    product = max(product, a*c);
    product = max(product, a*d);
    product = max(product, b*c);
    product = max(product, b*d);
    printf("%lld\n",product);
}

int main() {

    scanf("%lld", &a);
    scanf("%lld", &b);
    scanf("%lld", &c);
    scanf("%lld", &d);

    solve();

}

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

using namespace std;
using ll = long long;

using Field = vector<vector<int>>;
using Graph = vector<vector<int>>;
using VI = vector<int>;
using VC = vector<char>;
using PI = pair<int, int>;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) x.begin(), x.end()


int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n; cin >> n;
    vector<char> S(n);
    VI R(n);
    VI G(n);
    VI B(n);

    vector<char> color(3);

    ll ans = 0;

    int max_r = 0, max_g = 0, max_b = 0;

    REP(i, n) {
        cin >> S.at(i);
        if (S.at(i) == 'R') max_r++;
        else if (S.at(i) == 'G') max_g++;
        else if (S.at(i) == 'B') max_b++;
    }
    int num_r = 0, num_g = 0, num_b = 0;

    REP(i, n) {
        if (S.at(i) == 'R') num_r++;
        else if (S.at(i) == 'G') num_g++;
        else if (S.at(i) == 'B') num_b++;

        R.at(i) = max_r - num_r;
        G.at(i) = max_g - num_g;
        B.at(i) = max_b - num_b;

    }


    for (int i = 0; i < n-2; i++) {
        color.at(0) = S.at(i); 
        for (int j = i + 1; j < n-1; j++) {
            if (color.at(0) == S.at(j)) continue;
            color.at(1) = S.at(j);

            if ((color.at(0) == 'R' && color.at(1) == 'G') || (color.at(0) == 'G' && color.at(1) == 'R')) color.at(2) = 'B';
            else if ((color.at(0) == 'B' && color.at(1) == 'G') || (color.at(0) == 'G' && color.at(1) == 'B')) color.at(2) = 'R';
            else if ((color.at(0) == 'B' && color.at(1) == 'R') || (color.at(0) == 'R' && color.at(1) == 'B')) color.at(2) = 'G';

            if (color.at(2) == 'R') {
                ans += R.at(j);
                if ((j + j - i < n) && (S.at(j + j - i) == color.at(2))) ans--;
            }else if (color.at(2) == 'G') {
                ans += G.at(j);
                if ((j + j - i < n) && (S.at(j + j - i) == color.at(2))) ans--;
            }else if (color.at(2) == 'B') {
                ans += B.at(j);
                if ((j + j - i < n) && (S.at(j + j - i) == color.at(2))) ans--;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3704
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a, b, c = 0, 0, 0
L, R = [], []
for p in map(int, input().split()):
  if p < 0:
    a += 1
    L.append(p)
  elif p == 0:
    b += 1
  else:
    c += 1
    R.append(p)
L.sort()
R.sort()
s = a*c
t = b*(b-1)//2 + (a+c)*b
if s < k <= s+t:
  ans = 0
else:
  if k <= s:
    ok = -1
    ng = -(10**18+1)
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = 0
      temp = 0
      for l in L:
        while now < c and l*R[now] > mid:
          now += 1
        temp += c - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  else:
    ok = 10**18
    ng = 0
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = c - 1
      temp = s+t
      for i, r in enumerate(R):
        if now <= i:
          break
        while now > i and r*R[now] > mid:
          now -= 1
        temp += now - i
      now = 0
      for i in range(a-1, -1, -1):
        l = L[i]
        if now >= i:
          break
        while now < i and l*L[now] > mid:
          now += 1
        temp += i - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  ans = ok
print(ans)

Measured memory_bytes: 102216
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define REV(x) reverse(ALL(x))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ld = long double;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using Pll_ll = pair<ll, ll>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;
const double EPS = 1E-10;

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


bool isPalindrome(string s){
    int n = s.length();
    REP(i, n / 2){
        if(s[i] != s[n - i - 1]) return false;
    }
    return true;
}

int main(){
    string S; cin >> S;
    int N(S.length());
    bool okay(isPalindrome(S));
    okay = okay & isPalindrome(S.substr(0, (N-1)/2));
    okay = okay & isPalindrome(S.substr((N+3)/2 -1));
    cout << (okay ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353 
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int k;
string s;
int main(){
	cin >> k >> s;
	rep(i,s.size()){
		int x = s[i]-'A';
		x = (x+k)%26;
		cout << (char)('A'+x) ;
	}
	cout << endl;
	}

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

int main() {
    ll n, a, b;
    cin >> n >> a >> b;

    if (b < a || n==1 && a!=b) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = (b-a)*(n-1)-(b-a)+1;
    cout << ans << endl;
}

Measured memory_bytes: 3532
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
using namespace std;
typedef long long int llint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a%b, y, x);
	y -= a / b * x;
	return d;
}

bool check(int a, int b) {
	return a > b;
}

int main() {
	int n, k;
	cin >> n >> k;
	vint a(n, 0);
	int x;
	rep(i, n) {
		cin >> x;
		a[x - 1]++;
	}
	sort(a.begin(), a.end(), check);
	int cnt = 0;
	rep(i, k) {
		cnt += a[i];
	}
	cout << n - cnt << endl;
	return 0;
}

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

int SumOfDigit(int n){
    int sum = 0;
    while(n>0){
        sum += n%10;
        n /= 10;
    }

    return sum;
}

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

    int min = 1145141919;

    for(int i = 1; i < N; i++){
        int a = i;
        int b = N-a;

        int suma = SumOfDigit(a);
        int sumb = SumOfDigit(b);

        int sum = suma + sumb;

        if(min > sum) min = sum;
    }

    cout << min << endl;
}

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

using namespace std;

vector<int> G[100000];
int cnt_same[100000];

int main(){
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        int X;
        cin >> X;
        G[X%M].push_back(X);
    }
    for(int i = 0; i < M; i++){
        if(G[i].size() == 0) continue;
        sort(G[i].begin(), G[i].end());
        int prev = G[i][0];
        int cnt = 1;
        for(int j = 1; j < G[i].size(); j++){
            if(G[i][j] == prev) {
                cnt++;
                if(j == G[i].size()-1){
                    cnt_same[i] += (cnt/2)*2;
                }
            }
            else{
                cnt_same[i] += (cnt/2)*2;
                cnt = 1;
                prev = G[i][j];
            }
        }
    }
    int ans = 0;
    ans += G[0].size()/2;
    if(M%2 == 0) ans += G[M/2].size()/2;
    for(int i = 1; i < (M+1)/2 ; i++){
        //cout << G[i].size() << ' ' << G[M-i].size() << endl;
        if(G[i].size() > G[M-i].size()){
            ans += G[M-i].size();
            ans += min((int)(G[i].size()-G[M-i].size()), cnt_same[i])/2;
        }else{
            ans += G[i].size();
            //cout << ans << endl;
            ans += min((int)(G[M-i].size()-G[i].size()), cnt_same[M-i])/2;
            //cout << ans << endl;
        }
    }
    //cout << cnt_same[9] << endl;
    cout << ans << endl;
}

Measured memory_bytes: 5760
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void chmax(int &a, int b) { if (a < b) a = b; }

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

    int res = 0;
    vector<vector<int> > dp(N+1, vector<int>(N+1, 0));
    for (int i = N-1; i >= 0; --i) {
        for (int j = N-1; j > i; --j) {
            if (S[i] == S[j]) chmax(dp[i][j], dp[i+1][j+1] + 1);
            chmax(res, min(dp[i][j], j-i));
            //cout << dp[i][j];
        }
        //cout << endl;
    }
    cout << res << endl;
}

Measured memory_bytes: 98176
N, M = map(int, input().split())
correct = [False] * N
penalty = [0] * N

sum_AC, sum_WA = 0, 0
for i in range(M):
    p, s = input().split()
    p = int(p) - 1
    if correct[p]:
        continue
    if s == "AC":
        correct[p] = True
        sum_AC += 1
        sum_WA += penalty[p]
    else:
        penalty[p] += 1

print(sum_AC, sum_WA)


Measured memory_bytes: 4596
#!/usr/bin/env python3
import sys
import bisect

def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    A.sort()
    B.sort()
    C.sort()
    answer = 0
    for i in range(N):
        A_index = bisect.bisect_left(A,B[i])
        C_index = bisect.bisect_left(C,B[i]+1) 
        answer += (N-C_index)*A_index
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 24036
#include<iostream>  //bubbleSort
#include<utility>
using namespace std;
int main(){
    int n,A[101],j;  //nは要素の長さ
    int flag = 1;
    int i = 0;  //未ソート部分列の先頭インデックス
    int count = 0;
    
    cin >> n;
    for(int i = 0; i < n; i++){  //A[]に値を入れる
        cin >> A[i];
        //cout << A[i] << " ";
    }
    
    
    
    while (flag != 0){
        flag = 0;
        for(j = n-1; j > i ;j--){
            if(A[j] < A[j-1]){
                swap(A[j], A[j-1]);
                flag = 1;
                count++;
                
            }
            
        }
        
        //for(int k = 0; k < n; k++){
        //    cout << A[k] << " ";
        //}
        
        //cout << endl;
        
        i++;
    }
    
    
    
    
    for(int k = 0; k < n; k++){  // 表示
        //cout << A[k];
        if(k == n-1) cout << A[k];
        else cout << A[k] << " ";
        
    }
    
    cout << endl;
    cout << count << endl;   //回数の表示
    
    return 0;
}



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

typedef pair<int,int> P;
const int INF = 500000000;

int main(){
    int k,n;
    cin >> k >> n;
    int house[n];
    for (int i = 0; i < n; i++){
        cin >> house[i];
    }
    int len = house[0] + (k - house[n-1]);
    for (int i = 1; i < n; i++){
        len = max(len, house[i]-house[i-1]);
    }
    cout << k-len << "\n";
}

Measured memory_bytes: 1024
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
sys.setrecursionlimit(10*6)
INF = float("inf")


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return [i-N-1 for i in range(len(conc)) if Z[i] == N]


def solve(s: str, t: str):
    S = len(s)
    T = len(t)

    # Sの方が長くなるように
    if T > S:
        s *= int(math.ceil(T/S))

    s2 = s+s
    match = zfindall(s2, t)

    if len(match) == 0:
        print(0)
        return

    # グラフを構成し、最長パスが答え。ループがあれば-1
    # グラフは辞書で表現
    edges = {}
    rev_edges = {}
    for i, m in enumerate(match):
        if m >= S:
            continue
        edges[m] = (m+T) % S
        rev_edges[(m+T) % S] = m

    # 何度も同じ経路を確認するのを改善しうる
    maxlenpath = 1
    visitted = defaultdict(int)
    for k in edges:
        # kが含まれるパスを考える。
        # 逆向きにはったグラフを利用して、双方向の長さを求める
        if visitted[k]:
            continue
        counter = 0
        b = k
        while b in edges:
            counter += 1
            b = edges[b]
            if visitted[b]:
                print(-1)
                return
            else:
                visitted[b] = 1
        b = k
        while b in rev_edges:
            counter += 1
            b = rev_edges[b]
            if visitted[b]:
                print(-1)
                return
            else:
                visitted[b] = 1
        # print("visitted: ", visitted)
        # print("counter: ", counter)
        if maxlenpath < counter:
            maxlenpath = counter
    print(maxlenpath)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()


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

struct Node{
    int key;
    Node *next,*prev;
};

Node *nil;

void init(){
    nil=(Node *)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

Node* listSearch(int key){
    Node *cur = nil->next;
    while(cur!=nil && cur->key != key){
        cur = cur->next;
    }
    return cur;
}



void deleteNode(Node *t){
    if(t==nil)return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

void deleteFirst(){
  deleteNode(nil->next);
}

void deleteLast(){
    deleteNode(nil->prev);
}

void deleteKey(int key){
    deleteNode(listSearch(key));
}


void insert(int key){
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;

}

void printList(){
    Node *cur = nil->next;
    int i=0;
    while(1){
        if(cur==nil)break;
        if(i++>0)printf(" ");
            printf("%d",cur->key);
            cur=cur->next;
        
    }
    printf("\n");
}


int main(){
    int n,key;
    scanf("%d",&n);
    char com[22];
    init();
    
    for(int i=0;i<n;i++){
        scanf("%s %d",com,&key);
        if(com[0]=='i')insert(key);
        else if(com[0]=='d'){
            if(strlen(com)>6){
                if(com[6]=='F')deleteFirst();
                else if(com[6]=='L')deleteLast();           
            }
                            
        else deleteKey(key);

        
        }
        

        
    }
    
    printList();
    
}






Measured memory_bytes: 34452
#include<bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false);

long int solve(string s, int n) {
  long int res = 0;
  if(n <= 3) return res;
  //let i be middle element
  for(int i=1; i<n-1; i++) {
    long int r,g,b;
    long int r1,g1,b1;
    r = g = b= r1 = g1 = b1 = 0;
    for(int j=0; j<i; j++) {
      if(s[j] == 'R') {
        r++;
      } else if(s[j] == 'G') {
        g++;
      } else {
        b++;
      }
    }
    for(int j=i+1; j<n; j++) {
      if(s[j] == 'R') {
        r1++;
      } else if(s[j] == 'G') {
        g1++;
      } else {
        b1++;
      }
    }
    if(s[i] == 'R') {
      res += g*b1;
      res += b*g1;
    } else if(s[i] == 'G') {
      res += r*b1;
      res += b*r1;
     
    } else if(s[i] == 'B') {
      res += g*r1;
      res += r*g1;
    }
    //sub 
    int l = i-1;
    int rr = i+1;
    while(l >= 0 && rr < n) {
      if(s[l] != s[i] && s[l] != s[rr] && s[i] != s[rr]) {
        res--;
      }
      l--;
      rr++;
    }

  }
  return res;
}

int main() {
  FASTIO
  int n; cin >> n;
  string s; cin >> s;
  cout << solve(s, n) << "\n";
}

Measured memory_bytes: 3656
n = int(input())
s = list(str(input()))
s = [{ord(c)-ord('a')} for c in s]

def segfunc(x, y):
    return x | y

def init(init_val):
    # set_val
    for i in range(n):
        seg[i+num-1] = init_val[i]
    # built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res, seg[p])
        if q&1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res

# identity element
ide_ele = set()

# num: n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

init(s)

q = int(input())
for _ in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))

Measured memory_bytes: 477816
import java.io.*;
import java.util.*;
 
public class Main{
	
 
	public void solve(){
		int N = nextInt();
		long ans = 0;
		long pre = 0;
		for(int i = 1; i <= N; i++){
			long v = nextInt();
			if(v == 0){
				pre = 0;
				continue;
			}
			v += pre;
			ans += v / 2;
			pre = v % 2;
		}
		out.println(ans);
	}
	
	private static PrintWriter out;
	public static void main(String[] args){
		out = new PrintWriter(System.out);
		new Main().solve();
		out.flush();
	}
	
	
	
	public static int nextInt(){
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;
	}
	
	public static long nextLong(){
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}
	public static String next(){
		int c;
		while(!isAlNum(c = read())){}
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	
	
	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;
	private static int read(){
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return (bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}
	
	private static boolean isAlNum(int c){
		return '!' <= c && c <= '~';
	}
}

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n, W;
    cin >> n >> W;

    vector<int> w(n+1), v(n+1);
    for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    vector<vector<int>> dp(n+1,vector<int>(W+1,0));

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= W; j++){
            if(j - w[i] >= 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
            }
            dp[i][j] = max(dp[i][j],dp[i-1][j]);
        }
    }
    cout << dp[n][W] << endl;
}



Measured memory_bytes: 80256
X, Y = map(int, input().split())

def prepare(N, MOD):
    fac = [None] * (N+1)
    finv = [None] * (N+1)
    inv = [None] * (N+1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, N+1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
    return fac, finv

def comb_rem(N, K, fac, finv, MOD):
    if N < K:
        return 0
    if N < 0 or K < 0:
        return 0
    else:
        return fac[N] * (finv[K] * finv[N - K] % MOD) % MOD

MOD = 10 ** 9 + 7

if (X+Y)%3 != 0:
    print(0)
    exit()

if (2*X-Y)//3 < 0 or (2*Y-X)//3 < 0:
    print(0)
    exit()

fac, finv = prepare((X+Y)//3, MOD)
ans = comb_rem((X+Y)//3, (2*X-Y)//3, fac, finv, MOD)

print(ans)

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

def main():
    rows = []
    for i in range(3):
        row = list(map(int, input().split()))
        rows.append(row)

    for i in range(2):
        if not rows[i][0] - rows[i + 1][0] == rows[i][1] - rows[i + 1][1] == rows[i][2] - rows[i + 1][2]:
            return False
    for j in range(2):
        if not rows[0][j] - rows[0][j + 1] == rows[1][j] - rows[1][j + 1] == rows[2][j] - rows[2][j + 1]:
            return False
    return True

print("Yes" if main() else "No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	char s[50];
	for(int i=0;i<3;i++)
	{
		cin>>s;
		cout<<s[i];
	}
	cout<<endl;
	return 0;
}


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

int main(void)
{
    int n = 0;
    long long s[150000] = {0};
    int s4 = 0;
    int s2 = 0;
    int i = 0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%lld",&s[i]);
    }
    for(i=0;i<n;i++){
        if(s[i] % 4 == 0){
            s4++;
        }else if(s[i] % 2 == 0){
            s2++;
        }
    }
    if(s4*2 + s2 == n || s4 >= n / 2){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    
    return 0;
}

Measured memory_bytes: 1280
N=int(input())
L=[[0 for x in range(10)] for y in range(10)]

o=1
for i in range(1,N+1):
  if 10*o==i:
    o*=10
  y=i%10
  if y==0:
  	continue
  x=i//o
  L[x][y]+=1

t=0
for i in range(1,10):
  for j in range(1,10):
    t+=L[i][j]*L[j][i]

print(t)


Measured memory_bytes: 3064
fn main() {
    let s: String = read();
    let sl: usize = s.len();
    let sb = s.as_bytes();
    let srb = s.as_bytes();
    let mut ans = 0;
    for i in 0..sl {
        if sb[i] != srb[sl - i - 1] {
            ans += 1;
        }
    }
    println!("{}", ans / 2);
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <fstream>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <assert.h>
using namespace std;
#define eps 0.000000001
#define LONG_INF 10000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define seg_size 65536*4
#define REP(i,n) for(long long i = 0;i < n;++i)
int main() {
#define int long long
	int n;
	cin >> n;
	vector<int> hoge;
	REP(i, n) {
		int a;
		cin >> a;
		hoge.push_back(a - i - 1);
	}
	sort(hoge.begin(), hoge.end());
	long long pre_ans = 0;
	long long ans = 0;
	REP(i, n) {
		pre_ans += hoge[i] - hoge[0];
	}
	ans = pre_ans;
	for (int i = 1; i < n; ++i) {
		long long diff = hoge[i] - hoge[i - 1];
		pre_ans += diff * i;
		pre_ans -= diff * (n - i);
		ans = min(ans, pre_ans);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2420
N, K = gets.strip.split.map(&:to_i)

t = Array.new(K){0}

(1..N).each { |i| t[i % K] += 1 }

res = 0
K.times do |a|
  b = (K - a) % K
  c = (K - a) % K
  next if ((b + c) % K) != 0
  res += t[a] * t[b] * t[c]
end

puts res


Measured memory_bytes: 3324
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define OUT(x) cout << (x) << endl;
#define OUTA(a, n) \
    REP(i, n) { cout << (a[i]) << (i == n - 1 ? "\n" : " "); }
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll N;
vi D;
ll M;
vi T;

int main()
{
    cin >> N;
    D = vi(N);
    REP(i, N)
    {
        cin >> D[i];
    }
    cin >> M;
    T = vi(M);
    REP(i, M)
    {
        cin >> T[i];
    }

    map<ll, ll> cnt = map<ll, ll>();
    REP(i, N)
    {
        if (cnt.count(D[i]))
        {
            ++cnt[D[i]];
        }
        else
        {
            cnt[D[i]] = 1;
        }
    }
    bool ok = true;
    REP(i, M)
    {
        if (cnt.count(T[i]))
        {
            --cnt[T[i]];
            ok &= (cnt[T[i]] >= 0);
        }
        else
        {
            ok = false;
        }
    }
    string ans = ok ? "YES" : "NO";

    OUT(ans);
}

Measured memory_bytes: 15872
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner in = new java.util.Scanner(System.in);
		int A = in.nextInt();
		int B = in.nextInt();
		if(A<=8 && B<=8) {
			System.out.print("Yay!");
		}else {
			System.out.print(":(");
		}
		in.close();
		
	}
}

Measured memory_bytes: 21844
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10010
using namespace std;
int ans[N],w[N];
int nxt[N<<1],to[N<<1],head[N<<1],cnt;
void add(int u,int v)
{
	nxt[++cnt]=head[u];
	to[cnt]=v;
	head[u]=cnt;
}
int g[2][N];
void dfs(int u)
{
	for(int i=head[u];i;i=nxt[i]) dfs(to[i]);
	memset(g[0],0x3f,sizeof(g[0]));
	int now=0;
	g[now][0]=0;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
        int pre=now;
        now=!now;
        memset(g[now],0x3f,sizeof(g[now]));
        for(int j=0;j<=w[u];j++)
		{
            if(j>=w[v]) g[now][j]=min(g[now][j],g[pre][j-w[v]]+ans[v]);
            if(j>=ans[v]) g[now][j]=min(g[now][j],g[pre][j-ans[v]]+w[v]);
        }
	}
	for(int i=0;i<=w[u];i++) ans[u]=min(ans[u],g[now][i]);
}
int main()
{
	int n;
	scanf("%d",&n);
    for(int i=2;i<=n;i++)
	{
		int fa;
		scanf("%d",&fa);
        add(fa,i);
    }
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    memset(ans,0x3f,sizeof(ans));
    dfs(1);
    if(ans[1]<0x3f3f3f3f) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
    return 0;
}

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

int ans=200000;

int main(){
  
  int n;
  cin >> n;
  
  int rr=0;
  char wr[n];
  for(int i=0; i<n; i++){
    cin >> wr[i];
    if(wr[i] == 'R')rr++;
  }
  int lw=0;
  
  ans = min(ans,rr);
  
   for(int i=0; i<n; i++){

     if(wr[i] == 'R'){

       rr--;

     } else {

       lw++;

     }
     
     ans = min(ans,max(rr,lw));

   }
   
   cout << ans << endl;
   
}


Measured memory_bytes: 3812
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
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
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
mat = [[] for _ in range(n)]

for i in range(n-1):
    a,b,w=mii()
    mat[a-1].append([b-1,w])
    mat[b-1].append([a-1,w])

visited=[2]*n

def dfs(now,dist):
    #距離加算，判定
    #(now,dist)
    if dist %2==0:
        visited[now]=0
    else:
        visited[now]=1

    for i,j in mat[now]:
        if visited[i]!=2:continue
        dfs(i,dist+j)

dfs(0,0)
print(*visited)

Measured memory_bytes: 89208
//----------BHAVIK DIWANI(PICT_COMP)---------------
#include<bits/stdc++.h>
#include<stdlib.h>
#include<stdio.h>
#define test ll t; cin>>t; while(t--)
#define FOR(p,n) for(ll i=p;i<(ll)n;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define ll long long
#define int long long
#define ull unsigned long long
#define MAX 1000005
#define pb push_back
#define mkp make_pair
#define vi vector<int>
#define pii pair<int,int>
#define endl '\n'
#define vs vector<string>
#define mii map<int,int>
#define msi map<string,int>
#define vpii vector< pair<int, int > >
#define vpsi vector< pair< string ,int > >
#define forci(p,q) for(int i=p;i<q;i++)
ll gcd(ll a,ll b){ if(b==0) return a;    return gcd(b,a%b);}
ll lcm(ll a,ll b) { return (a/gcd(a,b)*b);}
ull power(ull a, ull b) {a %= mod;  ull res = 1;  while (b > 0) { if (b & 1) res = res * a % mod;  a = a * a % mod;  b >>= 1; }  return res%mod; }
ll modmul(ll x, ll y){return (x*y)%mod;}
ll modadd(ll x, ll y){return (x+y)%mod;}
ll modsub(ll x, ll y){return (x-y+mod)%mod;}
ll fact[1000007]={0};
void facto() {fact[0]=1;fact[1]=1;for(int i=2;i<100007;i++)fact[i]=(fact[i-1]*i)%mod;}
ll ncr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[r],mod-2)))%mod; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
ll npr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
inline long long toint(const std::string &s) {std::stringstream ss; ss << s; long long x; ss >> x; return x;}
inline std::string tostring(long long number) {std::stringstream ss; ss << number; return ss.str();}
inline std::string tobin(long long x) {return std::bitset<63>(x).to_string();}
/*bool prime[MAX];
ull sieve(){memset(prime,true,sizeof(prime));for(ull p=2;p*p<MAX;p++){if(prime[p]==true){for(ull i=2*p;i<MAX;i+=p){prime[i]=false;}}}prime[0]=0;prime[1]=0;
}*/
using namespace std;
void solve()
{
	string s;
	cin>>s;
	int q;
	cin>>q;
	deque<char> res;
	for(int i=0;i<s.size();i++)
		res.pb(s[i]);
	int cnt=0;
	while(q--)
	{
		int a;
		cin>>a;
		if(a==1)
			cnt++;
		else
		{
			int add;	cin>>add;
			char ch;	cin>>ch;
			if(cnt%2!=0)
			{
				if(add==2)
					res.push_front(ch);
				else
					res.pb(ch);
			}
			else
			{
				if(add==2)
					res.pb(ch);
				else
					res.push_front(ch);
			}
		}
	}
	if(cnt%2!=0)
	{
		for(auto it=res.rbegin();it!=res.rend();it++)
			cout<<*it;
	}
	else
	{
		for(auto it=res.begin();it!=res.end();it++)
			cout<<*it;
	}
}
signed main()
{
	fastio;
//	test
		solve();
}

Measured memory_bytes: 976
#include<cstdio>

using namespace std;

const int MA = 1100100;

long long N, P;

bool isPrime[MA];

void genPrimes(){
	for(int i = 0; i < MA; ++i) isPrime[i] = true;
	for(int i = 2; i < MA; ++i){
		if(isPrime[i]){
			for(int j = 2; i * j < MA; ++j){
				isPrime[i * j] = false;
			}
		}
	}
}

long long solve(){
	genPrimes();
	long long ans = 1;
	long long val = P;
	for(int i = 2; i < MA; ++i){
		int e = 0;
		if(!isPrime[i]) continue;
		while(val % i == 0){
			e++;
			val /= i;
		}
		int f = e / N;
		for(int j = 0; j < f; ++j){
			ans *= i;
		}
	}
	if(val > 1){
		if(N == 1) ans *= val;
	}
	return ans;
}

void input(){
	scanf("%lld%lld", &N, &P);
}

int main(){
	input();
	long long ans = solve();
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(i, x.size()) cerr << x[i] << (i == x.size() - 1 ? "\n" : " ")
using namespace std;
//#define int long long
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================
int N;
vector<int> A;
//=============================
void input()
{
    cin>>N;
    A.resize(N);
    rep(i,N){
        cin>>A[i];
    }

}
//=============================
void func() {}
//=============================
void solve()
{
    sort(A.begin(),A.end());
    cout<<abs(A[N-1]-A[0])<<endl;

}
//=============================
signed main()
{
    input();
    solve();
    return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

// {{{
template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar[0].size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}

template<typename T>
void unique(vector<T>& vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

template<typename T>
vector<T> cumsum(vector<T> vec){
    vector<T> newvec((T)vec.size());
    int tmp = 0;
    for (int i = 0; i < (int)vec.size(); i++) {
        tmp += vec[i];
        newvec[i] = tmp;
    }

    return newvec;
}

template<typename T>
T digitsum(T x){
    T y=0;
    while(x){
        y += x % 10;
        x /= 10;
    }

    return y;
}
// }}}
/* vim:set foldmethod=marker: */

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

    int ans=0, m=0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'I') {
            ans++;
            m = max(m, ans);
        }else{
            ans--;
        }
    }

    cout << m << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}

// sortの仕方
// int a[N];
// array<int,N> ar;
// vector<int> v;
//
// sort(a, a+N); // 配列
// sort(ar.begin(), ar.end()); // array
// sort(v.begin(), v.end()); // vector 昇順
// sort(v.begin(), v.end(), greater<int>()); // 降順

// Template
// template <class T>
// T foomax(T x, T y){
//   if (x > y){
//     return x;
//   }else{
//     return y;
//   }
// }

// string を int に変換 stoi("1010")
// int を string に変換 to_string(1010)


Measured memory_bytes: 256
#Get Everything
n,m=map(int,input().split())
ab=[]
c=[]
inf=float("inf")
for i in range(m):
    ab.append(list(map(int,input().split())))
    lst=list(map(int,input().split()))
    num=0
    for u in lst:
        num+=2**(u-1)
    c.append(num)
dp=[[inf]*(2**n) for _ in range(m+1)]
for i in range(m):
    dp[i][0]=0
for i in range(m):
    for j in range(2**n):
        if dp[i][j]!=inf:
            dp[i+1][j|c[i]]=min(dp[i+1][j|c[i]],dp[i][j]+ab[i][0])
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
if dp[m][2**n-1]!=inf:
    print(dp[m][2**n-1])
else:
    print(-1)

Measured memory_bytes: 174296
/*
Created on 13-09-20 17:30

@author: roastedcoder

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9+7;
const int INF = INT_MAX;
#define endl "\n"
#define pb push_back
#define roastedcoder ios_base::sync_with_stdio(false); cin.tie(NULL);
//__________________________________________________________________

vector <int> graph[100001];
bool vis[100001];

/*
void dfs(int node) {
	vis[node] = true;
	for(auto child : graph[node])
		if(!vis[child]) dfs(child);
}
*/

int main() {
	roastedcoder
	int x; cin>>x;
	x == 0 ? cout<<1 : cout<<0;
}

//__________________________________________________________________
/*
Sample Input:


Sample Output:


*/



Measured memory_bytes: 5984
#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if(a > b)
    {
        while(a > 0)
        {
            cout << b;
            a--;
        }
    }
    else
    {
        while(b > 0)
        {
            cout << a;
            b--;
        }
    }
    return 0;
}


Measured memory_bytes: 504
//Author- Vaibhav singh
//will be expert soon 
// *#####################################################################################*
#include<bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_multiset tree<long long , null_type,less_equal<long long >, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_set tree<long long , null_type,less<long long >, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
#define ll long long int
#define YES cout<<"YES"<<"\n";
#define NO cout<<"NO"<<"\n";
#define ld     long double
#define yes cout<<"yes"<<"\n";
#define no cout<<"no"<<"\n";
#define No cout<<"No"<<"\n";
#define Yes cout<<"Yes"<<"\n";
#define f(i,a) for(i=0;i<a;i++)
#define fo(i,a) for(i=1;i<=a;i++)
#define fa(i,a) for(auto i:a)
#define r(i,a) for(auto i=a.rbegin();i!=a.rend();i++)
#define en cout<<"\n";
#define ull unsigned long long int
#define o(x) cout<<x<<"\n";
#define o1(x) cout<<x<<" ";
#define pb push_back
#define F first
#define in insert
#define mp make_pair
#define S second
#define pre(n) cout<<fixed<<setprecision(n);
#define      gcd(a,b)    __gcd(a,b)
#define bs            binary_search
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define test ll t;cin>>t;while(t-->0)
const ll Mod = 998244353;
#define mod 1000000007
#define pi 3.14159265358979323846
#define re return 0;
// *#######################################################################################*
// *#########################################################################################*
    //      ll ans=0,b[5000005]={0},a[5000005],i,n,x=0;                
   //ll k,n,i;

    

int main()
{
      
      fast
     ll n,k,i;
  
   cin>>n>>k;
   
   ll a[k];
   f(i,k)
   {
         cin>>a[i];
   }
   ll p=1,e=n;
   while(p!=0)
   {  
         e=n;
         ll  r=1;
         while(n!=0)
         {
               ll z=n%10;
               f(i,k)
               {
                     if(a[i]==z)
                     {
                           r=0;
                           break;
                     }
               }
               n=n/10;
         }
       //  o(r)
       n=e;
         if(r==0)
         {
               n++;
         }
         
         
        
         else
         {
        p=0;      
         }
        // p--;
   }
   
   
   o(n)
   
   

    re
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
struct point{int x;int y;};
int i,j,k,count1=0,count2=0;

int main(){
    string s;
    long long int k;
    cin>>s>>k;
    int one=0;
    for(i=0;s[i]=='1';i++){one++;}
    if(k==1)cout<<s[0]<<endl;
    else if(k<=one)cout<<1<<endl;
    else cout<<s[one]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int gcd (int x, int y) {
    if (x < y) swap(x, y);
    if (y == 0) return x;
    return gcd(x % y, y);
}
int main() {
    int N, X;
    cin >> N >> X;
    vector<int> x(N+1);
    x.at(0) = X;
    for(int i = 1; i <= N; i++) cin >> x.at(i);
    sort(x.begin(), x.end());
    
    int D = 0;
    for(int i = 0; i < N; i++) {
        D = gcd(D, (x.at(i+1) - x.at(i)));
    }
    cout << D << endl;
}



Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
// #include <numeric>
using namespace std;

#define ll long long

ll gcd(ll a, ll b)
{
	return (a? gcd(b % a, a):b);
}

int main()
{
    ll a, b, n;
    cin >> a >> b;
    n = gcd(a, b);

    ll ans = 1;
    for (ll i = 2; i * i < n; i++)
    {
        if (!(n % i))
        {
            ans++;
            while (!(n % i)) n /= i;
        }
    }

    if (n != 1) ans++;
    cout << ans << "\n";
}

Measured memory_bytes: 3640
def inpl(): return list(map(int, input().split()))

H,W = inpl()
MAP = [inpl() for i in range(H)]

flag = False #コインを持っているか
ans = []
for y in range(H):
	if y%2 == 0:
		xx = range(W)
	else:
		xx = reversed(range(W))
	for x in xx:
		if flag:
			ans.append([by,bx,y,x])
		if MAP[y][x]%2 == 1:
			flag = not flag
		bx,by = x,y

print(len(ans))
for a,zu,nya,n in ans:
	print(a+1,zu+1,nya+1,n+1)


Measured memory_bytes: 26232