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

int main(void){
    int n; cin >> n;
    vector<int> a(n);
    int MAX, MIN, MAX_i, MIN_i;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(i == 0 || MAX < a[i]){
            MAX = a[i];
            MAX_i = i;
        }
        if(i == 0 || MIN > a[i]){
            MIN = a[i];
            MIN_i = i;
        }
    }

    int ans[2][100];
    int m = 0;

    if(MAX > 0 && MIN < 0){
        if(MAX + MIN > 0){
            for(int i = 1; i <= n; i++){
                ans[0][m] = i;
                ans[1][m] = MAX_i + 1;
                m++;
            }
            MAX += MAX;
            MIN += MAX;
        }else{
            for(int i = 1; i <= n; i++){
                ans[0][m] = i;
                ans[1][m] = MIN_i + 1;
                m++;
            }
            MIN += MIN;
            MAX += MIN;
        }
    }

    //cout << MAX << " " << MIN << endl;

    if(MIN >= 0){   //全て非負整数
        for(int i = 2; i <= n; i++){
            ans[0][m] = i;
            ans[1][m] = i - 1;
            m++;
        }
    }else if(MAX <= 0){  //すべて０以下
        for(int i = n; i > 1; i--){
            ans[0][m] = i - 1;
            ans[1][m] = i;
            m++;
        }
    }

    cout << m << endl;
    for(int i = 0; i < m; i++){
        cout << ans[1][i] << " " << ans[0][i] << endl;
    }
    /*for(int i = 0; i < m; i++){
        a[ans[0][i] - 1] += a[ans[1][i] - 1];
    }

    for(int i = 0; i < n; i++){
        cout << a[i] << " ";
    }
    cout << endl;
    */
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
#include<queue>
#include<map>
#include <fstream>
#include<set>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long

/// 15 01

    char cc[200010];

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

        int n,a,b,c,d;
        cin>>n>>a>>b>>c>>d;
        a--;
        b--;
        c--;
        d--;
        for(int i=0;i<n;i++) cin>>cc[i];
        bool is=true,gap=false;
        for(int i=0;i<n;i++){
            if( i>=a && i<d && cc[i]=='#' && cc[i+1]=='#' ){
                is=false;
                break;
            }
            if( i >= b && i<=d && cc[i]=='.'&&cc[i-1]=='.'&&cc[i+1]=='.' ){
                gap=true;
            }
        }
        if( is && d > c )cout<<"Yes"<<endl;
        else if( is && gap ) cout <<"Yes"<<endl;
        else cout<<"No"<<endl;

      return 0;
    }











Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>

const std::string ACGT = "ACGT";

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

    int ans = 0, cnt = 0;
    for (char c : S) {
        ++cnt;
        if (std::count(ACGT.begin(), ACGT.end(), c) == 0) cnt = 0;
        ans = std::max(ans, cnt);
    }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

const long long INF = 1e18;
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h, w;
    cin >> h >> w;
    if(h == 1 or w == 1) {
        cout << 1 << endl;
        return 0;
    }
    cout << (h * w + 1) / 2;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
#include <deque>
#define REP(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using itn = int;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;

int main() {

    int n;
    cin >> n;
    
    cout << 1110 - n << endl;

    return 0;

}

Measured memory_bytes: 256
H, W = map(int, raw_input().split(' '))

counts = {}
for h in xrange(H):
  for c in raw_input():
    counts[c] = counts.get(c, 0) + 1

odd = two = 0
for count in counts.itervalues():
  if count % 2 == 1:
    odd += 1
  elif count % 4 != 0:
    two += 1

if (H * W) % 2 == 1:
  # all odd
  ans = odd <= 1 and two <= (H-1)/2 + (W-1)/2
elif H % 2 == 1:
  ans = (odd == 0 and two <= W/2)
elif W % 2 == 1:
  # odd and even
  ans = (odd == 0 and two <= H/2)
else:
  # all even
  ans = (odd == 0 and two == 0)

print ['No', 'Yes'][ans]

Measured memory_bytes: 2692
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long N, ans=0;
  cin >> N;
  string S[N];
  long long M=0, A=0, R=0, C=0, H=0;
  for(int i=0; i<N; i++) {
    cin >> S[i];
    if(S[i][0]=='M') {
      M++;
    }
    if(S[i][0]=='A') {
      A++;
    }
    if(S[i][0]=='R') {
      R++;
    }
    if(S[i][0]=='C') {
      C++;
    }
    if(S[i][0]=='H') {
      H++;
    }
  }
  ans=M*A*R+M*A*C+M*A*H+M*R*C+M*R*H+M*C*H+A*R*C+A*R*H+A*C*H+R*C*H;
  cout << ans << endl;
}

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

int main() {
    vector<int> c(3);
    for (int i = 0; i < c.size(); i++)
	cin >> c[i];
    sort(c.begin(), c.end());
    cout << (c[0] + c[1] == c[2] ? "Yes" : "No") << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
 using namespace __gnu_pbds;
 using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
#define FIO                     ios_base::sync_with_stdio(false); cin.tie(0)
#define mod                     1000000007
#define setbits                 __builtin_popcount
#define gcd                     __gcd
#define rep(i,a,b)              for(int i=a;i<=b;i++)
#define repr(i,b,a)             for(int i=b;i>=a;i--)
#define forn(i,n)               for(int i=0;i<n;i++)
#define all(a)                  a.begin(), a.end()
#define in(a,b)                 ( (b).find(a) != (b).end())
#define pb                      push_back
#define fill(a,v)               memset(a, v, sizeof a)
#define endl                    "\n"
#define ff                      first
#define ss                      second
#define mp                      make_pair
#define minin(a)                *min_element (all(a))
#define maxin(a)                *max_element(all(a))
#define asort(c)                sort(all(c))
#define dsort(c)                sort(all(c), greater<int>()) 
typedef  long long                   ll;
typedef  vector<int>                 vi;
typedef  pair<int, int>              ii;
typedef  vector<ii>                 vii;
typedef  set<int>                    si;
typedef  unordered_map<int, int>    mii;
typedef  vector<ll>                 vll;

const int N = 5e3 + 10;

long double a[N],p[N];

clock_t time_p=clock();
void timer()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

int main()
{
  FIO;
 

  int n,last;
  cin>>n;

  int mark=-2,ans=0;

  stack<int> s;

  forn(i,n)
  {
    cin>>last;
    s.push(last);
  }

  last=s.top();
  s.pop();

  while(!s.empty())
  {
    int cur=s.top();
    s.pop();

    if(cur>last)
    {
      if(mark==-2)
        mark=1;
      else if(mark==-1)
      {
        mark=-2;
        ans++;
      }
    }
    else if(cur<last)
    {

      if(mark==-2)
        mark=-1;
      else if(mark==1)
      {
        mark=-2;
        ans++;
      }
    }

    last=cur;
    
  }
  cout<<ans+1;
  return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(){
  int N;
  int a,b,d;
  char str[10];
  char s,c;

  fgets(str,10,stdin);
  sscanf(str,"%d",&N);

  printf("0\n");
  fflush(stdout);

  fgets(str,10,stdin);
  
  if(str[0]=='V')
    return 0;
  
  s = str[0];
  a = 1;
  b = N-1;
  
  int n=0;
  while(1){
    if(n++>30) break;
    d = b - a;
    printf("%d\n",d/2+a);
    fflush(stdout);
    fgets(str,10,stdin);  
    if(str[0]=='V') break;

    if ((d/2)%2==0 && s==str[0])
      b = a+d/2-1;
    if ((d/2)%2==0 && s!=str[0]){
      a = a+d/2+1;
      s = str[0];
    }
    if ((d/2)%2!=0 && s!=str[0])
      b = a+d/2-1;
    if ((d/2)%2!=0 && s==str[0]){
      a = a+d/2+1;
      s = str[0];
    }
    
  }

  
  return 0;
}


Measured memory_bytes: 848
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	long long n,c,k;
	long long  a[100000+10];
	cin>>n>>c>>k;
	for(long long i=1;i<=n;i++)cin>>a[i];
	a[n+1]=2e9+1; 
	sort(a+1,a+n+1);
	long long f=1;
	long long ren=1;
	long long bus=1;
	for(long long i=2;i<=n;i++){
		if(a[i]-a[f]>k){f=i;ren=1;bus++;continue;}
		if(i-f+1>c){f=i;ren=1;bus++;continue;}
		ren++;
	}
	cout<<bus<<endl; 
	return 0;
} 

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

def if_YYMM(text):
    yy = int(text[0:2])
    mm = int(text[2:4])
    
    if mm < 1 or mm > 12:
        return False
    
    return True

def if_MMYY(text):
    mm = int(text[0:2])
    yy = int(text[2:4])
    
    if mm < 1 or mm > 12:
        return False
    
    return True

text = input()

mmyy = if_MMYY(text)
yymm = if_YYMM(text)

if mmyy & yymm:
    print("AMBIGUOUS")
elif mmyy:
    print("MMYY")
elif yymm:
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static class Node {
		int value;
		Node prev;
		Node next;
		
		public Node(int value, Node prev, Node next) {
			this.value = value;
			this.prev = prev;
			this.next = next;
		}
	}
	
	static class MyList {
		Node start;
		Node end;
		
		public void insert(int num) {
			Node tmp = new Node(num, end.prev, end);
			end.prev.next = tmp;
			end.prev = tmp;
		}
		
		public StringBuilder print() {
			Node tmp = start.next;
			StringBuilder sb = new StringBuilder();
			while (tmp != end) {
				sb.append(tmp.value);
				sb.append(' ');
				tmp = tmp.next;
			}
			
			return sb;
		}
		
		public void splice(MyList myList) {
			this.end.prev.next = myList.start.next;
			myList.start.next.prev = this.end.prev;
			this.end = myList.end;
		}
		
		public MyList() {
			start = new Node(-1000000001, null, null);
			end = new Node(-1000000001, start, start);
			start.next = end;
			start.prev = end;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();
		List<MyList> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			list.add(new MyList());
		}
		for (int i = 0; i < q; i++) {
			switch (sc.nextInt()) {
				case 0:
					list.get(sc.nextInt()).insert(sc.nextInt());
					break;
				case 1:
					String str = list.get(sc.nextInt()).print().toString();
					if (str.length() <= 0) {
						System.out.println();
					} else {
						System.out.println(str.substring(0, str.length() - 1));
					}
					break;
				case 2:
					int s = sc.nextInt();
					int t = sc.nextInt();
					list.get(t).splice(list.get(s));
					list.set(s, new MyList());
					break;
			}
		}
	}
}



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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FORD(i,b,a) for (int i = (int)(b) - 1; i >= a; --i)
#define REP(i,N) FOR(i,0,N)
#define st first
#define nd second
#define pb push_back

typedef pair<int, int> PII;
typedef long long LL;

char S[105][105];

int main() {
  scanf("%s", S[0]);
  int N = strlen(S[0]);
  int result = 105;
  FOR(c,'a','z'+1) {
    bool any = false;
    REP(i,N) if (S[0][i] == c) any = true;
    if (!any) goto done;
    REP(i,105) {
      bool all = true;
      REP(j, N-i) all = all && (S[i][j] == c);
      REP(j, N-i-1) S[i+1][j] = (S[i][j] == c || S[i][j+1] == c) ? c : c + 1;
      if (all) {
        result = min(result, i);
        goto done;
      }
    }
    done:;
  }

  printf("%d\n", result);
}


Measured memory_bytes: 764
#include <stdio.h>

int main(){
    int a,b,c,sum;

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

    sum = a + b + c;

    if(a >= b && a >= c){
        sum -= a;
    }
    else if(b >= a && b > c){
        sum -= b;
    }
    else if(c >= a && c >= b){
        sum -= c;
    }

    printf("%d",sum);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int input, count = 0;
  cin >> input;
  if(input == 0){
    cout << count << endl;
  }else{
    if(input / 100 == 1){
      count++;
      input -= 100;
    }
    if(input / 10 == 1){
      count++;
      input -= 10;
    }
    count += input;
    cout << count << endl;
  }
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

const int L = 6;
const int MaxN = 2000000;
const int M = 1000000007;

inline int modpow(int a, const int &n)
{
	int res = 1;
	for (int i = n; i; i >>= 1)
	{
		if (i & 1)
			res = (s64)res * a % M;
		a = (s64)a * a % M;
	}
	return res;
}

int fact[MaxN + 1];
int rfact[MaxN + 1];

inline void init_fact(int n = MaxN)
{
	fact[0] = 1;
	for (int i = 1; i <= n; ++i)
		fact[i] = (s64)fact[i - 1] * i % M;

	rfact[n] = modpow(fact[n], M - 2);
	for (int i = n; i; --i)
		rfact[i - 1] = (s64)rfact[i] * i % M;
}

int dx[L];
int dy[L];

inline int binom(int n, int m)
{
	return (s64)fact[n] * rfact[m] % M * rfact[n - m] % M;
}

inline int calc(int x, int y, int p, int q)
{
	return binom(p - x + q - y, p - x);
}

inline int query(int x, int y, int p, int q)
{
	int ret = 0;
	for (int i = dx[2]; i <= dx[3]; ++i)
		ret = ((ret - (s64)calc(x, y, i, dy[2] - 1) * calc(i, dy[2], p, q) % M * (i + dy[2] - 1)) % M + M) % M;
	for (int i = dx[2]; i <= dx[3]; ++i)
		ret = (ret + (s64)calc(x, y, i, dy[3]) * calc(i, dy[3] + 1, p, q) % M * (i + dy[3])) % M;
	for (int i = dy[2]; i <= dy[3]; ++i)
		ret = ((ret - (s64)calc(x, y, dx[2] - 1, i) * calc(dx[2], i, p, q) % M * (i + dx[2] - 1)) % M + M) % M;
	for (int i = dy[2]; i <= dy[3]; ++i)
		ret = (ret + (s64)calc(x, y, dx[3], i) * calc(dx[3] + 1, i, p, q) % M * (i + dx[3])) % M;
	return ret;
}

int main()
{
	init_fact();

	for (int i = 0; i < L; ++i)
		cin >> dx[i];
	for (int i = 0; i < L; ++i)
		cin >> dy[i];

	--dx[0], ++dx[5];
	--dy[0], ++dy[5];

	int res = 0;
	for (int s = 0; s < 1 << 4; ++s)
	{
		int u = s >> 0 & 1, p = s >> 2 & 1;
		int v = s >> 1 & 1, q = s >> 3 & 1;

		int ways = query(dx[u], dy[v], dx[p | 4], dy[q | 4]);
		if (u ^ v ^ p ^ q)
			ways = (M - ways) % M;

		res = (res + ways) % M;
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 15872
#AC

from collections import deque

n=int(input())
G=[[]]
for i in range(n):
    G.append(list(map(int,input().split()))[2:])

#bfs(木でないかも)
L=[-1]*(n+1)
q=deque()

L[1]=0
q.append(1)
while q:
    now=q.popleft()
    L.append(now)
    for next in G[now]:
        #探索済み
        if L[next]>=0:
            continue
        #探索予定(なくて良い)
        #if next in q:
        #    continue
        q.append(next)
        L[next]=L[now]+1

for i in range(1,n+1):
    print(i,L[i])



Measured memory_bytes: 6036
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
void readA(T)(size_t n,ref T[]t){t=new T[](n);auto r=rdsp;foreach(ref v;t)pick(r,v);}
void readM(T)(size_t r,size_t c,ref T[][]t){t=new T[][](r);foreach(ref v;t)readA(c,v);}

void main()
{
  int n; readV(n);
  int[][] a; readM(n, 3, a);

  auto dp = new int[][](n, 3);
  dp[0] = a[0];

  foreach (i; 1..n)
    foreach (j; 0..3)
      foreach (k; 0..3)
        if (j != k)
          dp[i][j] = max(dp[i][j], dp[i-1][k] + a[i][j]);

  writeln(dp[$-1].reduce!max);
}


Measured memory_bytes: 10492
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
	int N, K;
	cin >> N >> K;

	set<int> st;
	st.insert(1);
	rep(i, N) {
		set<int> st2;
		for (int num : st) {
			st2.insert(num * 2);
			st2.insert(num + K);
		}
		st = st2;
	}

	cout << *st.begin() << endl;

    return 0;
}


Measured memory_bytes: 256
A, B = list(input().split())
s = B.strip().split(".")
a = int(s[0]) * (10 ** 2)
if len(s) > 1:
    t = s[1] + "0" * (2 - len(s[1]))
    a += int(t)
a = int(a)
ans = a * int(A) // 100
print(ans)

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

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

    vector<string> s(n);
    vector<int> t(n);
    for(int i=0; i<n; i++){
        cin >> s[i] >> t[i];
    }

    string x;
    cin >> x;

    int ans = 0;
    bool flag = false;
    for(int i=0; i<n; i++){
        if(flag == true) ans += t[i];
        if(s[i] == x) flag = true;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3504
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>

using namespace std;

#define l first
#define r second

int n, k;
int a[500000];
long long b[500000];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    long long ans = 0;
    for (int i = 1; i < 31; i++)
    {
        if ((1 << i) & k)
        {
            int kek = k - (1 << i);
            kek |= (1 << i) - 1;
            long long s = 0;
            for (int j = 0; j < n; j++)
            {
                if ((kek | a[j]) == kek)
                {
                    s += b[j];
                }
            }
            ans = max(ans, s);
        }
    }
    int kek = k;
    long long s = 0;
    for (int j = 0; j < n; j++)
    {
        if ((kek | a[j]) == kek)
        {
            s += b[j];
        }
    }
    ans = max(ans, s);
    cout << ans;
}

Measured memory_bytes: 3456
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int A = scanner.nextInt();
        int B = scanner.nextInt();
        int C = scanner.nextInt();
        int X = scanner.nextInt();


        int cnt = 0;

        for(int i=0; i<=A; i++){
            for(int j=0; j<=B; j++){
                for(int k=0; k<=C; k++){
                    if(500*i + 100*j + 50*k == X){
                        cnt++;
                    }
                }
            }
        }

        System.out.println(cnt);


    }
}


Measured memory_bytes: 23252
X,Y, A,B,C = list(map(int,input().split()))
p = list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))


p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
s = p[0:X] + q[0:Y] + r

s.sort(reverse=True)
ans = 0

for i in range(X+Y):
    ans += s[i]
    
print(ans)


Measured memory_bytes: 23328
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
long A[400];
long DP[400*400];
void Calc(){
	int N = rei();
	for(int i=0;i<N;i++){
		A[i] = rel();
	}
	for(int i=1;i<N;i++){
		for(int j=0;j+i<N;j++){
			long ans = 1000000000000000000;
			for(int k=j;k<j+i;k++){
				ans = min(ans,DP[j*400+k]+DP[(k+1)*400+j+i]);
			}
			for(int k=j;k<=j+i;k++){
				ans += A[k];
			}
			DP[j*400+(i+j)] = ans;
		}
	}
	cout << DP[N-1] << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 1536
#include "bits/stdc++.h"
using namespace std;
int gcd(int a, int b){
    if(a<b) swap(a,b);
    int r = a%b;
    while(r>0){
        a = b;
        b = r;
        r = a%b;
    }
    return b;
}
int main(){
    int N,X,a,b,i,D;
    cin >> N >> X;
    cin >> b;
    D = abs(X-b);
    for(i=1;i<N;i++){
        cin >> b;
        a = abs(X-b);
        D = gcd(D,a);
    }
    cout << D << endl;
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> d(1e5+1);
  rep(i,n) {
    int x;
    cin >> x;
    d[x]++;
  }
  int ans = 0;
  int sum = 0;
  for (int i = 1; i <= 1e5; i++) {
    sum += d[i];
    if (sum == n-sum) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3788
number=[]
number=list(map(int,input()))

bad=0
good=0
for i in range(len(number)-1):
    tmp=number[i]
    if tmp is  number[i+1]:
        bad+=1
    else:
        good+=1

if bad >= 1:
    print("Bad")
elif good is 3:
    print("Good")



Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int main (){
    long long int a,b,k; cin >> a >> b >> k;
    if (k > a){
        cout << 0 << endl;
    }
        else {
        cout << a - k << endl;
    }
    if (k > (a+b)) cout << 0 << endl;
    else if(k > a){
       cout << a + b - k << endl;
    }
    else{
        cout << b << endl;
    }
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<55;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=2000005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

int x,y;

int main(){
	cin>>x>>y;
	if((x+y)%3!=0){
		cout<<0<<endl;
		return 0;
	}
	ll t=(x+y)/3;
	x-=t,y-=t;
	if(x<0||y<0){
		cout<<0<<endl;
		return 0;
	}
	Init();
	cout<<nCk(x+y,x)<<endl;
}

Measured memory_bytes: 15872
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
 int A,B,x,y,z;
 cin>> A >> B;
 x=A*B;
 y=A-B;
 z=A+B;
if (x>y&&x>z)
    cout<<x<<endl;
else if (y>z&&z>x)
    cout<<y<<endl;
else
    cout<<z<<endl;
}

Measured memory_bytes: 256
s = list(input())
if s == s[::-1]:
    pass
else:
    print("No")
    exit()
x = s[0:int((len(s)-1)/2)]
if x == x[::-1]:
    pass
else:
    print("No")
    exit()
x = s[int((len(s)+3)/2)-1:len(s)]
if x == x[::-1]:
    pass
else:
    print("No")
    exit()
print("Yes")


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

#define max 100

int main()
{
    int a, b, c;
    
    scanf("%d %d %d", &a, &b, &c);
    
    if (b/a>=c) {
        printf("%d", c);
    } else {
        printf("%d", b/a);
    }
    
    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int K = sc.nextInt();
		int X = sc.nextInt();
		
		int min = Math.max(-1000000, X-(K-1));
		int max = Math.min(1000000, X+(K-1));
		
		for(int i=0;i<max-min+1;i++) {
			int p = min + i;
			System.out.print(p);
			if(p != max) {
				System.out.print(" ");
			}
		}
		
		sc.close();	
	}
}

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

int main() {
  string S, T;
  cin >> S >> T;
  
  int N;
  
  N = S.size();
  
  int i = 0;
  
  while ( i < N ) {
  if ( S.at(i) == T.at(i) ){
  i++;
  continue;
  }
  
  else {
  cout << "No" << endl;
  break;
  }
}
  if (i == N){
    cout << "Yes" << endl;
  }

}


Measured memory_bytes: 3596
#include <iostream>
using namespace std;
int A, B, C;
int X, Y;
void Solve()
{
    int ans = 2000000005;
    for(int i = 0; i <= max(X, Y); i++)
    {
        int val = C * i * 2 + A * max(0, (X - i)) + B * max(0, (Y - i));
        ans = min(ans, val);
    }
    cout << ans << "\n";
}
int main()
{
    cin >> A >> B >> C >> X >> Y;
    Solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;


int n,m,k,a[200005],b[200005],dp1[200005],dp2[200005],ans;

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=1;i<=m;i++){
        cin >> b[i];
    }
    for(int i=1;i<=n;i++){
        dp1[i] = a[i];
        dp1[i] += dp1[i-1];
    }
    for(int i=1;i<=m;i++){
        dp2[i] = b[i];
        dp2[i] += dp2[i-1];
    }
    int ans = 0;
    for(int i=0;i<=n;i++){
        int curr = dp1[i];
        int l = 0, r = m;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(dp2[mid] <= k - dp1[i]){
                ans = max(ans,i+mid);
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
    }
    rc(ans);
}





Measured memory_bytes: 9904
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long m = sc.nextLong();

		PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
		for(int i=0; i<n; i++){
			pq.add(sc.nextLong());
		}
		for(int i=0; i<m; i++){
			Long a = pq.poll();
			a = a/2;
			pq.add(a);
		}
		long ans = 0;
		while(pq.size() > 0){
			ans += pq.poll();
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 64508
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.LongStream;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int H = sc.nextInt();
        int W = sc.nextInt();

        System.out.println(solve(H, W));

        sc.close();
    }

    static int solve(int H, int W) {
        if (H % 3 == 0 || W % 3 == 0) {
            return 0;
        }

        return Math.min(cut1(H, W), cut1(W, H));
    }

    static int cut1(int side1, int side2) {
        long result = Long.MAX_VALUE;
        for (int s1 : new int[] { side1 / 3, side1 / 3 + 1 }) {
            for (long[] restAreas : new long[][] { cut2(side1 - s1, side2), cut2(side2, side1 - s1) }) {
                long[] areas = LongStream.concat(LongStream.of((long) s1 * side2), Arrays.stream(restAreas)).sorted()
                        .toArray();

                result = Math.min(result, areas[2] - areas[0]);
            }
        }

        return (int) result;
    }

    static long[] cut2(int side1, int side2) {
        return new long[] { side1 / 2L * side2, (long) side1 * side2 - side1 / 2L * side2 };
    }
}

Measured memory_bytes: 28756
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int n; cin >> n;
    ll ans = 0;
    for (int i = 1; ; i++)
    {
        if (i*i > n) {
            cout << (i-1)*(i-1) << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)
#define what_is(x) cerr << #x << " is " << x << endl;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define inf std::numeric_limits<int>::max();
#define highest_2_pow(n)  __builtin_clzll((long long)0)- __builtin_clzll((long long)n) - 1
//-----------------------------------------------------------------------------------------------------
#define lli long long int 
#define int long long
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define vi vector<int>
#define vlli vector<long long int>
#define si set<int>
#define slli set<long long int>
#define mt make_tuple
#define mp make_pair
#define eb emplace_back
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
//---------------------------------------------------
using namespace std;
// GCD and LCM are available
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << endl;
err(++it, args...);
}

void faster(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}
int primeFactors(int n)  
{  
    set<int> s;
    while (n % 2 == 0)  
    {  
        s.insert(2);
        n = n/2;  
    }  
  
    // n must be odd at this point. So we can skip  
    // one element (Note i = i +2)  
    for (int i = 3; i <= sqrt(n); i = i + 2)  
    {  
        // While i divides n, print i and divide n  
        while (n % i == 0)  
        {  
            s.insert(i);  
            n = n/i;  
        }  
    }  
  
    // This condition is to handle the case when n  
    // is a prime number greater than 2  
    if (n > 2)  
        s.insert(n);
    return s.size(); 
}  
void solve(){
    int a,b;
    cin>>a>>b;
    int g = __gcd(a,b);
    cout<<primeFactors(g)+1<<endl;

}
signed main()
{
    faster();
    int t=1;
    //cin>>t;
    while(t--) solve();
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc170/tasks/abc170_c

#include <bits/stdc++.h>
using namespace std;
#define watch(x) cerr << (#x) << " is " << (x) << endl;
#define endl '\n' 
#define pii pair<int, int>
#define fi first
#define se second
signed main() {
    ios::sync_with_stdio(0);
    cin.sync_with_stdio(0);
    cin.tie(0);

    int X, N;
    cin >> X >> N;

    set<int> p;
    for(int i = 1; i <= N; i++) {
        int a;
        cin >> a;

        p.emplace(a);
    }

    pii ans = {INT_MAX, INT_MAX};
    for(int i = -1e5; i <= 1e5; i++) {
        pii x = pii(abs(X-i), i);

        if(!p.count(i)) {
            ans = min(ans, x);
        }
    }

    cout << ans.se << endl;
}


Measured memory_bytes: 3624
S = list(input())
A, B = int(S[0]+S[1]), int(S[2]+S[3])
if(0<A<13):
    if(0<B<13):
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if(0<B<13):
        print("YYMM")
    else:
        print("NA")

Measured memory_bytes: 3060
import sys

N, Y = list(map(int, input().split()))
x, y, z = -1, -1, -1
money = 0
for i in range(N + 1):
    for j in range(N - i + 1):
        if Y == i * 10000 + j * 5000 + (N - i - j) * 1000:
            print(i, j, N - i - j)
            sys.exit()

print(x, y, z)


Measured memory_bytes: 3060
loop do
    n = gets.to_i
    break if n == 0
    names, weights, powers = (1..n).map { gets.split }.transpose.map.with_index {|a, i| i > 0 ? a.map(&:to_i) : a}
    weight_sum = (0..2**n-1).map {|x| (0..n-1).map {|i| x[i] == 1 ? weights[i] : 0}.inject(:+)}

    g = Array.new(2**n, Float::INFINITY)
    g[0] = 0.0
    min_by = Array.new(2**n)
    min_by[0] = []

    (1..2**n-1).each do |x|
        (0..n-1).each do |i|
            if x[i] == 1
                y = x - (1 << i)
                next unless g[y]
                w = weight_sum[y]
                next if powers[i] < w
                m = w * (g[y] + 1.0) / (weights[i] + w)
                if m < g[x]
                    g[x] = m
                    min_by[x] = [i] + min_by[y]
                end
            end
        end
    end
    puts min_by[-1].map {|i| names[i]}
end



Measured memory_bytes: 7308
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

int main(){

    ll N, K, flg[10] = {};
    cin >> N >> K;
    rep(i, K){
        ll x;
        cin >> x;
        flg[x] = 1;
    }
    for(ll i = N; ; i++){
        ll f = 1;
        string s = to_string(i);
        for(ll j = 0; j < s.size(); j++)if(flg[s[j] - '0'])f = 0;
        if(f){
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}

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

using namespace std;
using ll = long long;

template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_V(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_M(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}

int main() {
    int n;
    cin>>n;
    V<string>s;
    for (int i = 0; i < n; ++i) {
        string ss;
        cin>>ss;
        sort(ss.begin(), ss.end());
        s.push_back(ss);
    }
    sort(s.begin(), s.end());


    ll ans = 0LL;
    ll cnt=1;
    s.push_back("#");
    string target=s[0];
    for (int i = 1; i < n+1; ++i) {
        if(s[i]==target){
            cnt++;
        }else{
            if(cnt>1){
                ans+=cnt*(cnt-1)/2;
            }
            target=s[i];
            cnt=1;
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 5748
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let x: i64 = sc.read();
    let mut b: Vec<i64> = vec![0; n];
    let mut l: Vec<i64> = vec![0; n];
    let mut u: Vec<i64> = vec![0; n];
    for i in 0..n {
        b[i] = sc.read();
        l[i] = sc.read();
        u[i] = sc.read();
    }

    if b.iter().all(|&b| b == 0) {
        println!("0");
        return;
    }

    let mut ok = (n as i64) * x;
    let mut ng = 0;
    while ok - ng > 1 {
        let total = (ok + ng) / 2;
        if solve(total, x, &b, &l, &u) {
            ok = total;
        } else {
            ng = total;
        }
    }

    println!("{}", ok);
}

fn solve(total: i64, x: i64, b: &Vec<i64>, l: &Vec<i64>, u: &Vec<i64>) -> bool {
    let n = b.len();
    let mut lower_sum = 0;
    let mut affect = vec![];
    for i in 0..n {
        lower_sum += l[i] * b[i];
        affect.push((x * u[i] - b[i] * (u[i] - l[i]), b[i], l[i], u[i]));
    }
    affect.sort();
    affect.reverse();

    let head = (total / x) as usize;
    let remain = total - total / x * x;

    let mut head_sum = 0;
    for i in 0..head {
        head_sum += affect[i].0;
    }
    let last = affect[head].0;
    for i in 0..n {
        let (_, b, l, u) = affect[i];
        let e = if remain >= b {
            remain * u - b * (u - l)
        } else {
            remain * l
        };
        if i < head {
            if head_sum + last - affect[i].0 + e >= lower_sum {
                return true;
            }
        } else {
            if head_sum + e >= lower_sum {
                return true;
            }
        }
    }
    false
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define out(x) cout << x << endl;
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
template <typename T>
T v1sum(vector<T> vec){
    T ret = 0;
    for(int i = 0; i < vec.size(); i++) ret += vec[i];
    return ret;
}
template <typename T>
vector<T> v1sort(vector<T> vec, bool min_to_max=true){
    sort(vec.begin(), vec.end(), [min_to_max](const T a, const T b){return (min_to_max == true) ? (a < b) : (b < a);});
    return vec;
}
template <typename T>
void v1show(vector<T> vec){
    for(int i = 0; i < vec.size(); i++){
        cout << vec[i] << " ";
    }
    cout << endl;
}
int main(){
    int a, b;
    cin >> a >> b;
    if(a < b){
        cout << 0 << endl;
    }else{
        cout << 10 << endl;
    }


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

typedef tree<
        int,
        null_type,
        less<int>,
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;



int main() {
//    cout << fixed << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n;
    cin >> n;
    map<string, int> d;
    int maxi = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ++d[s];
        maxi = max(maxi, d[s]);
    }

    for (auto e : d) {
        if (maxi == e.second) cout << e.first << '\n';
    }


}

Measured memory_bytes: 23808
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
#define foreach(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
using namespace std;
int n,i,j,ans[200005];
vector<int> e[200005];
int count(int x,int fa,int s){
	int sz=1;
	foreach(e[x],i){
		if(*i!=fa&&*i<=s) sz+=count(*i,x,s);
	}
	return sz;
}
void dfs(int x,int fa,int s0,int s1){
	if(fa){
		if(x>s1){
			ans[x]=ans[fa]+count(x,fa,s0);
		}
		else if(s0>s1){
			ans[x]=ans[fa]+count(x,fa,s0)-count(x,fa,s1);
		}
		else{
			ans[x]=ans[fa];
		}
	}
	foreach(e[x],i){
		if(*i!=fa) dfs(*i,x,max(s0,x),max(s1,fa));
	}
}
int main(){
	cin>>n;
	rep(i,n-1){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0,1,1);
	rep(i,n)if(i-1)cout<<ans[i]<<' ';
	return 0;
}

Measured memory_bytes: 27748
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
const int MOD = 1e9+7;
int mpow(int a,int b,int p=MOD){a=a%p;int res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1;}return res%p;}
const int N=20;

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);

      int n;
      cin>>n;
      string s;
      cin>>s;
      int ans=0;
      // int n=s.length();
      for(int i=0;i<n;i++)
      {
        int j=i;
        while(j<n&&s[j]==s[i]) j++;
        ans++;
        i=j-1;
      }
      cout<<ans;
}
// I never lose. I either win or I learn

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

class Point {
public:
	int x;
	int y;
	void set(int, int);
	int getx();
	int gety();
};
void Point::set(int newx, int newy){
	x = newx;
	y = newy;
}
int Point::getx(){
	return x;
}
int Point::gety(){
	return y;
}

int main()
{
	int N, n, d, xmax, xmin, ymax, ymin;
	Point p[200];
	while(cin >> N, N){
		p[0].set(0, 0);
		for(int i = 1; i < N; i++){
			cin >> n >> d;
			switch (d){
			case 0:
				p[i].set(p[n].getx()-1, p[n].gety());
				break;
			case 1:
				p[i].set(p[n].getx(), p[n].gety()-1);
				break;
			case 2:
				p[i].set(p[n].getx()+1, p[n].gety());
				break;
			case 3:
				p[i].set(p[n].getx(), p[n].gety()+1);
				break;
			}	
		}
		xmax = -1000;
		xmin = 1000;
		ymax = -1000;
		ymin = 1000;
		for(int i = 0; i < N; i++){
			if(p[i].getx() > xmax)
				xmax = p[i].getx();
			if(p[i].gety() > ymax)
				ymax = p[i].gety();
			if(p[i].getx() < xmin)
				xmin = p[i].getx();
			if(p[i].gety() < ymin)
				ymin = p[i].gety();
		}
		cout<<xmax - xmin + 1<<" "<< ymax - ymin + 1<<endl;

	}
	return 0;
}

Measured memory_bytes: 1160
/// referenced: https://beta.atcoder.jp/contests/abc066/submissions/2252964
#include <iostream>
using namespace std;

#define MOD 1000000007

int64_t pow(int64_t x,int64_t e){
  if(e==1) return x%MOD;
  if(e==0) return 1;
  return pow(x*x%MOD,e/2)*(e%2==0?1:x)%MOD;
}
int64_t inv(int64_t i){
  return pow(i,MOD-2);
}
int64_t fact[100002],factinv[100002];
int64_t C(int64_t n,int64_t r){
  return fact[n]*factinv[r]%MOD*factinv[n-r]%MOD;
}

int main(){
  int64_t n,a;
  bool c[100002];
  for(int64_t i=1;i<=n;i++) c[i]=false;
  int64_t p[100002];
  int64_t x,y;

  cin >> n;
  for(int64_t i=0;i<=n;i++){
    cin >> a;
    if(c[a]){
      x=p[a];
      y=i;
    }
    c[a]=true;
    p[a]=i;
  }


  fact[0]=1;
  for(int64_t i=1;i<=n+1;i++) fact[i]=i*fact[i-1]%MOD;
  for(int64_t i=0;i<=n+1;i++) factinv[i]=inv(fact[i]);

  for(int64_t i=1;i<=n+1;i++){
    int64_t ans;
    ans=C(n+1,i);
    if(i-1<=n-(y-x)) ans+=MOD-C(n-(y-x),i-1);
    cout << (ans%MOD) << endl;
  }

  return 0;
}


Measured memory_bytes: 3584
#include <cstdio>

int main(){
    int n,x;
    scanf("%d %d",&n,&x);
    int m[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&m[i]);
    }
    for(int i = 0; i < n; i++){
        x -= m[i];
    }
    int min = m[0];
    for(int i = 0; i < n; i++){
        if(m[i] < min){
            min = m[i];
        }
    }
    printf("%d\n",n + x / min);

    return 0;
}

Measured memory_bytes: 256
n,k=gets.split.map(&:to_i)
a,f=[gets,gets].map{|x|x.split.map(&:to_i).sort}
p (0..9**13).bsearch{|x|t=0;n.times{|i|a[-i-1]>x/f[i]&&t+=a[-i-1]-x/f[i]};t<=k}

Measured memory_bytes: 34284
n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
b = sorted(a)
m = b[n-2]
M = b[n-1]
if M == m:
  for i in range(n):
    print(M)
else:
  for i in range(n):
    if a[i] == M:
      print(m)
    else:
      print(M)

Measured memory_bytes: 14112
import java.util.Scanner;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
       
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        String[] ans = new String[a];
        for(int i = 0; i < a; i++){
            ans[i] = sc.next() + "_" + (1100 - sc.nextInt() ) + "_" + (i + 1);
        }
        Arrays.sort(ans);
        for(int i = 0; i < a; i++){
            String[] s =  ans[i].split("_");
            System.out.println(s[2]);
        }
    }
}

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

int main() {
  int n;
  cin>>n;
  int a[n],b[n];
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    a[i]=k;
  }
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    b[i]=k;
  }
  int p=0,q=0;
  for(int i=0;i<n;i++){
    int k=1;
    for(int j=1;j<n-i;j++)k*=j;
    p+=(k*a[i]);
    for(int m=i+1;m<n;m++){
      if(a[m]>a[i])a[m]--;
    }
  }
  for(int i=0;i<n;i++){
    int k=1;
    for(int j=1;j<n-i;j++)k*=j;
    q+=(k*b[i]);
    for(int m=i+1;m<n;m++){
      if(b[m]>b[i])b[m]--;
    }
  }
  cout<<abs(p-q)<<endl;
}


Measured memory_bytes: 256