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


int main() {
    string S; cin >> S;
    if (S.size() == 1) {
        cout << 0 << endl;
        return 0;
    }

    int num_flip_zero_start = 0;
    int key = 0;
    for (auto ch : S) {
        if((int)ch - '0' != key) num_flip_zero_start++;
        key ^= 1;
    }

    int num_flip_one_start = 0;
    key = 1;
    for (auto ch : S) {
        if((int)ch - '0' != key) num_flip_one_start++;
        key ^= 1;
    }

    int ans = min(num_flip_zero_start, num_flip_one_start);
    cout << ans << endl;
    return 0;
}


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

typedef int_fast32_t int32;
typedef int_fast64_t int64;

const int32 inf = 1e9+7;
const int32 MOD = 1000000007;
const int64 llinf = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define all(obj) (obj).begin(),(obj).end()
#define rall(obj) (obj).rbegin(),(obj).rend()
#define fi first
#define se second
#define pb(a) push_back(a)
typedef pair<int32,int32> pii;
typedef pair<int64,int64> pll;

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int32 n;
  cin >> n;
  int64 ans = 0;
  FOR(i,1,n+1){
    ans += (n-1) / i;

  }
  ANS(ans);
  return 0;
}

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

#ifdef _DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif

using namespace std;

int main() {
    string N;
    cin >> N;
    vector<int> ns;
    for (int i = 0; i < N.size(); ++i) {
        ns.push_back(N[i] - '0');
    }
    vector<vector<int>> dp(ns.size(), vector<int>(2, numeric_limits<int>::max()));
    
    for (int c = 0; c <= 1; ++c) {
        for (int d = 0; d <= 9; ++d) {
            dp[0][c] = min(dp[0][c], (ns[0] + d + c >= 10 ? 1 : 0) + (ns[0] + d + c) % 10 + d);
        }
        int x = dp[0][c];
        debug(x);
    }
    for (int i = 1; i < dp.size(); ++i) {
        for (int c = 0; c <= 1; ++c) {
            debug(i); debug(c);
            dp[i][c] = numeric_limits<int>::max();
            for (int d = 0; d <= 9; ++d) {
                dp[i][c] = min(dp[i][c], (ns[i] + d + c >= 10 ? dp[i - 1][1] : dp[i - 1][0]) + (ns[i] + d + c) % 10 + d);
            }
            int x = dp[i][c];
            debug(x);
        }
    }
    cout << dp.back()[0] << endl;
}

Measured memory_bytes: 60024
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed a , b , C = ~(1<<31), M = (1<<16)-1;
void init(signed A,signed B){a=A;b=B;}
signed r() {
  a = 36969 * (a & M) + (a >> 16);
  b = 18000 * (b & M) + (b >> 16);
  return (C & ((a << 16) + b)) % 1000000;
}

struct Point{
  Int x,y,z;
  Point(){}
  bool operator==(const Point &a)const{
    return x==a.x&&y==a.y&&z==a.z;
  }
  bool operator<(const Point &a)const{
    if(x!=a.x) return x<a.x;
    if(y!=a.y) return y>a.y;
    return z>a.z;
  }
};

signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int m,n,A,B;
  while(cin>>m>>n>>A>>B,m||n){
    init(A,B);
    
    vector<Point> ps(m+n);
    for(Int i=0;i<m;i++) cin>>ps[i].x>>ps[i].y>>ps[i].z;
    for(Int i=m;i<m+n;i++){
      ps[i].x=r();
      ps[i].y=r();
      ps[i].z=r();
    }
    n+=m;
    sort(ps.begin(),ps.end());
    using P = pair<Int, Int>;
    vector<set<P> > dp(n+1);
    
    auto print=[&](const set<P> &sp){
      for(auto p:sp) cout<<p.first<<" "<<p.second<<endl;
      cout<<endl;
    };
    
    auto veri=[&](const set<P> &sp){
      return;
      P a(-1,1e7);
      for(auto p:sp){
	assert(a.first<p.first);
	assert(a.second>p.second);
	a=p;
      }
    };
    
    auto check=[&](Int k,P p)->Int{
      if(dp[k].empty()) return 0;
      veri(dp[k]);
      auto it=dp[k].lower_bound(P(p.first,-1));
      if(it!=dp[k].begin()) --it;
      //if(it!=dp[k].begin()&&it->first>=p.first) --it;
      return it->first<p.first && it->second<p.second;
    };
    
    auto push=[&](Int k,P p){
      veri(dp[k]);
      if(dp[k].count(p)) return;
      dp[k].emplace(p);
      
      auto it=dp[k].lower_bound(p);
      while(it!=dp[k].end()){
	auto uk=it;uk++;
	if(uk==dp[k].end()) break;
	if(it->second<=uk->second){
	  dp[k].erase(uk);
	  it=dp[k].lower_bound(p);
	  continue;
	}
	break;
      }
      while(it!=dp[k].begin()){
	auto uk=it;uk--;
	if(uk->second<=it->second){
	  it=dp[k].erase(it);
	  if(it==dp[k].end()) break;
	  continue;
	}
	break;
      }
      
      veri(dp[k]);
    };
    
    for(Int i=0;i<n;i++){
      //cout<<ps[i].x<<" "<<ps[i].y<<" "<<ps[i].z<<endl;
      
      P p(ps[i].y,ps[i].z);
      Int l=0,r=i+1;
      while(l+1<r){
	Int m=(l+r)>>1;
	if(check(m,p)) l=m;
	else r=m;
      }
      push(l+1,p);
      //veri(dp[l+1]);
      
      if(0){
	cout<<l+1<<endl;
	for(Int j=0;j<=n;j++){
	  cout<<j<<":"<<endl;
	  print(dp[j]);
	}
      }
    }
    
    Int ans=1;
    while(ans<n&&!dp[ans+1].empty()) ans++;
    cout<<ans<<endl;
  }
  
  return 0;
}




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

int a[26];

int main(void){
	int i;
	char str[1201];
	
	while(scanf("%s",str) != EOF){
		
		for(i=0;i<strlen(str);i++){
			if('a' <= str[i] && str[i] <= 'z'){
				a[str[i]-'a']++;
			}
			else if('A' <= str[i] && str[i] <= 'Z'){
				a[str[i]-'A']++;
			}
		}
	}
	for(i=0;i<26;i++) printf("%c : %d\n",'a'+i,a[i]);
	return 0;
}

Measured memory_bytes: 540
#include<cstdio>

int main(){
    unsigned N;
    scanf("%u", &N);
    unsigned a[N], sum = 0;
    for(int i = 0; i < N; ++i){
        scanf("%u", a + i);
        sum ^= a[i];
    }
    sum ^= a[0];
    printf("%u", sum);
    for (size_t i = 1; i < N; i++)
    {
        printf(" %u", sum ^= (a[i-1] ^ a[i]));
    }
    printf("\n");
	return 0;
}

Measured memory_bytes: 3268
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long double PI = acos(-1.0);
// cout << fixed << setprecision(14);
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int A[N];
	int ans = 0;
	rep(i,N) cin >> A[i];
	rep(i,N){
		if(i % 2 == 0 && A[i] % 2 == 1) ++ans;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3648
c = []
3.times do
    c << gets.chomp.split(" ").map(&:to_i)
end

def check_row(ary)
    ary[0].zip(ary[1]).map{|x| x.inject(&:-)}.uniq.length == 1 && ary[0].zip(ary[2]).map{|x| x.inject(&:-)}.uniq.length == 1
end

answer = check_row(c) && check_row(c.transpose)

puts answer ? 'Yes' : 'No'

Measured memory_bytes: 1788
N=110000
dp=[0]*N

n=int(input()) 
h=list(map(int,input().split()))
now=[0,0,0]
for i in range(1,n):
    if i==1:
        dp[i]=dp[i-1]+abs(h[i]-h[i-1])
    else:
        now=[i,i-1,i-2]
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))

print(dp[n-1])

Measured memory_bytes: 53104
l, r = list(map(int, input().split(' ')))

if r - l >= 2019:
    ans = 0
else:
    ans = l * r % 2019
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            mod = i * j % 2019
            if mod < ans:
                ans = mod

print(ans)

Measured memory_bytes: 3060
n, k = map(int, input().split())
kadan = [list(map(int, input().split())) for _ in range(n)]

left = 0
right = 10**18*2
while right -left > 1:
    mid = (right+left)//2
    cnt = 0
    for i in range(n):
        if mid >= kadan[i][0]:
            cnt += (mid - kadan[i][0])//kadan[i][1] + 1
    if k > cnt :
        left = mid 
    elif k <= cnt :
        right = mid 
print(right)



Measured memory_bytes: 89884
#include<stdio.h>
#define MAX 100005

int parent[MAX],left[MAX],right[MAX],n, D[MAX];

int getDepth(int u);
void setDepth(int u,int p);
void printChildren(int u);

int main(){
  int i,j,d,v,c,l,r,w,t;
  
  scanf("%d",&n);
  for(i=0;i<n; i++){
    parent[i] = -1;
    left[i] = -1;
    right[i] = -1;   
  }
  
  for(i = 0; i < n; i++){
    scanf("%d",&v);
    scanf("%d",&d);
    for(j = 0; j < d; j++){
      scanf("%d",&c);
      if(j == 0){
	left[v] = c;
      }
      else{
	right[l] = c;
      }
      l =c;
      parent[c] = v;
    }
  }

  for(w = 0; w< n; w++){
    if (parent[w] == -1 ) r = w;
  }
  setDepth(r,0);
  for(t = 0; t < n; t++)printChildren (t);
  return 0;
}

int getDepth(int u){
  int d = 0;
  while(parent[u] != -1){
    u = parent[u];
    d++;
  }
  return d;
}


void setDepth(int u, int p){
  D[u] = p;
  if(right[u] !=-1){
    setDepth(right[u],p);
  }
  if(left[u] != -1){
    setDepth(left[u],p+1);
  }
}
void printChildren(int u){
  int i,c;
  printf("node %d: ", u);
  printf("parent = %d, ", parent[u]);
  printf("depth = %d, ", getDepth(u));
  if(parent[u] == -1){
    printf("root, ");
  }
  else if (left[u] == -1){
    printf("leaf, ");
  }
  else{
    printf("internal node, ");
  }
  printf("[");
  for(i = 0, c = left[u]; c !=-1 ; i++,c = right[c]){
    if(i)printf(", ");
    printf("%d",c );
  }
  printf("]\n");
}



Measured memory_bytes: 6408
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;
const int MOD = 1000000007;

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

  int n; cin >> n;
  vi a(n); rep(i, n) cin >> a[i];

  int query; cin >> query;

  for (int i = 0; i < query; ++i) {
    int b, e, k; cin >> b >> e >> k;
    int cnt = 0;
    for (int j = b; j < e; ++j) {
      cnt += a[j] == k;
    }
    cout << cnt << '\n';
  }

  return 0;
}


Measured memory_bytes: 3188
#include<iostream>
#include<cmath>

using namespace std;

#define MIN 9999999
#define NUM 4

int main(){
    int a,b,c,d;
    int judge = MIN;
    int res = 0;

    cin>>a>>b>>c>>d;

    res = abs((a+b) - (c+d));
    if(res<judge) judge = res;

    res = abs((a+c) - (b+d));
    if(res<judge) judge = res;

    res = abs((a+d) - (b+c));
    if(res<judge) judge = res;

    cout<<judge<<endl;

    return 0;
}


Measured memory_bytes: 3096
from collections import defaultdict
N = int(input())
S = input()
rgb_list = [[] for i in range(3)]
rgb2index = {'R':0, 'G':1, 'B':2}
for i, s in enumerate(S):
    rgb_list[rgb2index[s]] += [i]
rgb_list = sorted(rgb_list, key=len)
other_index = set(rgb_list[2])
ans = 0
len_other = len(other_index)
count = 1
for i in rgb_list[0]:
    for j in rgb_list[1]:
        diff = abs(i-j)
        tmp = - int((min(i, j) - diff) in other_index) - int((max(i, j) + diff) in other_index)
        if diff % 2 == 0 and (max(i, j) - diff//2) in other_index:
            tmp -= 1
        ans += len_other + tmp
print(ans)

Measured memory_bytes: 74616
#include <iostream>
#include <cstring>
#include <cstdlib>

const int MAX = 1000;

class Stack
{
    private:
        int S[MAX];
        int sp;

    public:
        Stack()
        {
            sp = 0;
        }

        void push(int x)
        {
            S[sp++] = x;
        }

        int pop()
        {
            return S[--sp];
        }
};

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

    Stack stack;
    int x;
    char op[100];

    while (std::cin >> op) {
        int a,b;
        if (strcmp(op, "+") == 0) {
            a = stack.pop();
            b = stack.pop();
            stack.push(a + b);
        }
        else if (strcmp(op, "-") == 0) {
            a = stack.pop();
            b = stack.pop();
            stack.push(b - a);
        }
        else if (strcmp(op, "*") == 0) {
            a = stack.pop();
            b = stack.pop();
            stack.push(a * b);
        }
        else {
            stack.push(std::atoi(op));
        }
    }
    std::cout << stack.pop() << std::endl;
}



Measured memory_bytes: 3168
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int A,B;
const int c[5]={0,300000,200000,100000,0};
int main(){
	A=read(),B=read();
	if(A==1&&B==1){
		return !printf("1000000\n");
	}
	A=min(A,4),B=min(B,4);
	printf("%d\n",c[A]+c[B]);
	return 0;
}



Measured memory_bytes: 3680
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


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


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define Return(expr) { Cout(expr); return 0; }
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, n);
    unordered_map<char, int> k;
    cin >> k['A'] >> k['B'] >> k['C'];
    Cins(string, n, s);
    
    vc<char> ans;
    For(i, n){
        char x = s[i][0], y = s[i][1];
        if(k[x] == 0 && k[y] == 0) Return("No");
        if(k[x] == 0){
            k[x] ++, k[y] --, ans.push_back(x);
            // Cout(y, " -> ", x, " : ", k['A'], " ", k['B'], " ", k['C']);
        }
        else if(k[y] == 0 || i == n-1){
            k[y] ++, k[x] --, ans.push_back(y);
            // Cout(x, " -> ", y, " : ", k['A'], " ", k['B'], " ", k['C']);
        }
        else if(k[x] == 1 && Contains(s[i+1], x)){
            k[x] ++, k[y] --, ans.push_back(x);
            // Cout(y, " -> ", x, " : ", k['A'], " ", k['B'], " ", k['C']);
        }
        else{
            k[y] ++, k[x] --, ans.push_back(y);
            // Cout(x, " -> ", y, " : ", k['A'], " ", k['B'], " ", k['C']);
        }
    }
    Cout("Yes");
    For(i, n) Cout(ans[i]);
}


Measured memory_bytes: 6732
from copy import deepcopy
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions
from operator import itemgetter
import itertools
import copy


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
s = input()
if s == 'ABC':
    print('ARC')
else:
    print('ABC')


Measured memory_bytes: 95760
#include<bits/stdc++.h>
using namespace std;
int n,k,ans=0;
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		if(k<=x)
			++ans;
	}
	cout<<ans<<endl;
	return 0;
} 

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
import pdb
     
def main():
    N = S()
    K = I()
    dp = [[[0 for _ in range(102)] for __ in range(2)] for ___ in range(102)]
    dp[0][0][0] = 1
    for i in range(1, len(N)+1):
        for j in range(2):
            if j == 1:
                max_dig = 9
            else:
                max_dig = int(N[i-1])
            for k in range(i+1):
                for d in range(max_dig + 1):
                    if d < max_dig:
                        # kakutei
                        miman = 1
                    else:
                        miman = 0
                        if j == 1:
                            miman = 1
                    if d != 0:
                        newK = k + 1
                    else:
                        newK = k
                    dp[i][miman][newK] += dp[i-1][j][k]

    print(dp[len(N)][0][K] + dp[len(N)][1][K])
main()



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

int main() {
	string S;
	cin >>S;
	int count[4]{ 0,0,0,0 };
	for (int i = 0;i < 4;i++) {
		for (int ii = 0;ii <= S.length();ii++) {
			if (S[i] == S[ii]) {
				count[i]++;
			}
		}
	}


	for (int i = 0;i < 4;i++)
	{
		if (count[i] != 2) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;

	return 0;
}


Measured memory_bytes: 256
n, k = [int(v) for v in input().split()]

c = (n - 1) * (n - 2) // 2
#print("c=", c)
m = 0
if k > c:
  print(-1)
else:
  m_max = n - 1 + (c - k)
  print(m_max)
  for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
      if m < m_max:
        print(i, j)
        m += 1
      else:
        break

Measured memory_bytes: 3608
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}



fn main() {
    let a: f32 = read();
    let buf = a / 60.0;
    let buf_int = buf as i32;
    let sec = ((buf - buf_int as f32) * 60.0).round();

    let min_buf = buf_int as f32 / 60.0;
    let hour = min_buf as i32;
    let min = ((min_buf - hour as f32) * 60.0).round();

    println!("{}:{}:{}", hour, min, sec);
}



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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;

int main(){

    string s,t;
    cin>>s>>t;

    cout<<t+s<<"\n";

    return 0;

}

Measured memory_bytes: 256
/* ex 9_2
   Tarara */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE (int)(1e5 + 10)

//リストのノード（スタック内の各データ）の定義
typedef struct node{
    char elem;
    struct node *next;
} node;

//スタックにデータを追加
void push(node **first, char elem){
    //追加する分の領域を確保
    node *new = calloc(1, sizeof(node));
    if(new == NULL) exit(1);
    new->elem = elem;
    new->next = *first;
    *first = new;
}

//スタックからデータを取り出す
char pop(node **first){
    char elem;
    node *tmp = *first;
    if(tmp == NULL) exit(1);
    elem = tmp->elem;
    *first = tmp->next;
    //取り出したノードのメモリを解放
    free(tmp);
    return elem;
}

int main(void){
    int count = 0;
    char input[SIZE];
    int i;
    //最初のノードの指す先
    node *first = NULL;

    scanf("%s", input);

    // 次の要素がある場合

    for(i = 0; i < strlen(input); i++)
    {
        push(&first, input[i]);
        if (first->next != NULL && first->elem != first->next->elem)
        {
            count += 2;
            pop(&first);
            pop(&first);
        }
    }

    printf("%d\n", count);
    return 0;
}

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

s = input()
N = len(s)

t = ""
for X in s:
	if X != "x":
		t += X

if t != t[::-1]:
	print(-1)
	exit()

s2 = s[::-1]

i = 0
j = 0
ans = 0

while i < N and j < N:
	if s[i] == s2[j]:
		i += 1
		j += 1
	else:
		if s[i] == "x":
			i += 1
		else:
			j += 1
		ans += 1

ans += (N - i)*(i < N) + (N - j)*(j < N)

print(ans//2)


Measured memory_bytes: 5464
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }
void Taka() { cout << "Takahashi" << endl; }
void Aoki() { cout << "Aoki" << endl; }
void digit(int d) { cout << fixed << setprecision(d); }
void IOup() { cin.tie(0); ios::sync_with_stdio(false); }

int a[100010];
bool v[100010];

int main() {
	int n;

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

	int p = 1, cnt = 0;
	v[1] = true;
	while (1) {
		cnt++;

		p = a[p];
		if (p == 2)
			break;

		if (v[p]) {
			cnt = -1;
			break;
		}

		v[p] = true;
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <utility>
#include <math.h>

using namespace std;

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

  vector<pair<int, int>> balls;

  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    balls.push_back(pair<int, int>(x, i));
  }

  int total = 0;
  for (int i = 0; i < n; i++) {
    pair<int, int> ball = balls[i];
    int x = ball.first, y = ball.second;

    int amove = x * 2;
    int bmove = abs(x - k) * 2;
    total += min(amove, bmove);
  }
  cout << total << "\n";
}


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

#define fo(i, n) for(int i=0; i<n; i++)
#define Fo(i, k, n) for(int i=k; i<n; i++)
#define endl "\n"

int main() {

	int n, w, temp1, temp2;
	cin >> n >> w;

	long dp[n + 1][w + 1];
	fo(i, n + 1) fo(j, w + 1) dp[i][j] = 0;

	vector<pair<int, int>> item;
	fo(i, n) {
		cin >> temp1 >> temp2;
		item.push_back(make_pair(temp1, temp2));
	}

	Fo(i, 1, n + 1) {
		Fo(j, 1, w + 1) {
			temp1 = item[i - 1].first;
			if (j >= temp1) {
				dp[i][j] = max(dp[i - 1][j], item[i - 1].second + dp[i - 1][j - temp1]);
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	cout << dp[n][w];
	// fo(i, n + 1) {
	// 	fo(j, w + 1) cout << dp[i][j] << " ";
	// 	cout << endl;
	// }

	return 0;
}

Measured memory_bytes: 82528
import sys
s = input()
# まず達成可能かどうかを判定する
s_without_x = [si for si in s if si != 'x']
if len(s_without_x) % 2 == 0:
    if s_without_x[:len(s_without_x)//2] != s_without_x[len(s_without_x)-1:len(s_without_x)//2-1:-1]:
        print(-1)
        sys.exit(0)
else:
    if s_without_x[:len(s_without_x)//2] != s_without_x[len(s_without_x)-1:len(s_without_x)//2:-1]:
        print(-1)
        sys.exit(0)

# 達成可能な場合
l = 0
r = len(s) - 1
cnt = 0
while l < r:
    if s[l] != s[r]:
        cnt += 1
        if s[l] == 'x':
            l += 1
        else:
            r -= 1
    else:
        l += 1
        r -= 1
print(cnt)

Measured memory_bytes: 4852
#include <bits/stdc++.h>
#define nmax 200000
using namespace std;
int a[nmax],p[nmax],k;
void ciur()
{
    
    for(int i=2;i<nmax;i++){
        if(p[i]==0){
            k++;
            a[k]=i;
            for(int j=2*i;j<nmax;j+=i){
                p[j]=1;
            }
        }
    }
}
int main()
{
  int x,sol=0;
  cin>>x;
  ciur();
 
  int mij,st=1,dr=k;
  while(st<=dr){
      mij=(st+dr)/2;
      if(a[mij]==x){
          sol = mij;
          st = dr+1;
      }
      else{
          if(a[mij]>x){
            sol=mij; 
            dr=mij-1;  
          }
          else{
              st=mij+1;
          }
      }
  }
  cout<<a[sol];
}


Measured memory_bytes: 1152
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
string S;
int main() {
	cin>>S;

	int ans =0;
	if(S[0]=='1')ans++;
	if(S[1]=='1')ans++;
	if(S[2]=='1')ans++;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	int n,k;
	vector<int> ice(10);
	while(1){
		cin >> n;
		if(n==0) break;
		for(int i=0;i<10;i++) ice[i]=0;
		for(int i=0;i<n;i++){
			cin >> k;
			ice[k]+=1;
		}
		for(int i=0;i<10;i++){
			if(ice[i]==0) cout << "-" << endl;
			else{
				for(int j=0;j<ice[i];j++) cout << "*";
				cout << endl;
			}
		}
		ice.clear();
	}
	return 0;
}

Measured memory_bytes: 1184
import java.util.Scanner;
public class Main
{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int K = sc.nextInt();
    int R = sc.nextInt();
    int Rating = 0;
    int Result = 0;
    if(K < 10)
    {
      Rating = 100 * (10 - K);
      Result = R + Rating;
      System.out.println(Result);
    }
    else
    {
      System.out.println(R);
    }
  }
}


Measured memory_bytes: 35612
# 解説を参考に作成


# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N):
    ans = 0
    for i in range(1, N + 1):
        ans += (i + i * (N // i)) * (N // i) // 2
    print(ans)


if __name__ == '__main__':
    N = int(input())
    solve(N)
    # print(prime_factorization(10000000))
    pass


Measured memory_bytes: 9004
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 100000000;
const int MAX_N = 50;
using namespace std;
int main() {
	int A, B, K;
	cin >> A >> B >> K;
  		map<int,int>mp;
	if (B - A + 1 <= K) {
		for (int i = A; i <= B; i++) {
			cout << i << endl;
		}
	}
	else {
      	int x=K;
		while (x > 0) {
			mp[A]++;
			A++;
			x--;
		}
		x = K;
		while (x > 0) {
			mp[B - K + 1]++;
			B++;
			x--;
		}
		for (auto p : mp) {
			int x = p.second;
			if (x>0) {
				cout << p.first << endl;
			}
		}
    }
}








Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
        cout.precision(20);
    }
} fast;

/* define */
#define FOR(I, X, Y) for (long long(I) = (X); (I) < (Y); (I)++)
#define REP(I, X, Y) for (long long(I) = (Y)-1; (I) >= (X); (I)--)
#define ALL(X) (X).begin(), (X).end()
#define pb push_back
#define COUNT(V, X)                           \
    (upper_bound((V).begin(), (V).end(), X) - \
     lower_bound((V).begin(), (V).end(), X))
#define debug(x) cerr << #x << ':' << x << endl;
#define DEBUG(v)                             \
    {                                        \
        cerr << #v << ':';                   \
        for (auto xv : v) cerr << xv << ' '; \
        cerr << endl;                        \
    }
#define Yes(X) cout << (X ? "Yes" : "No") << endl;
#define YES(X) cout << (X ? "YES" : "NO") << endl;
#define ctoi(C) (C - '0')
#define pow2(x) ((long long)((long long)1 << x))

/* alias */
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const long long dx[] = {1, 0, -1, 0};
const long long dy[] = {0, 1, 0, -1};
const long long dx8[] = {1, 1, 0, -1, -1, -1, 0, 1};
const long long dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};
const long long dx9[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
const long long dy9[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const int INF = 1000000007;
const long long LINF = 1000000000000000007;

/* func */
template <typename T1, typename T2>
inline bool chmin(T1 &a, const T2 &b) {
    if (a > b) a = b;
    return a > b;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, const T2 &b) {
    if (a < b) a = b;
    return a < b;
}
long long max(long long x, int y) {
    return max(x, (long long)y);
}
long long max(int x, long long y) {
    return max((long long)x, y);
}
long long min(long long x, int y) {
    return min(x, (long long)y);
}
long long min(int x, long long y) {
    return min((long long)x, y);
}

/* library */

/* main */

signed main() {
    ll N, T;
    cin >> N >> T;
    vector<pair<ll, ll>> v(N);
    for (size_t i = 0; i < N; i++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end());
    ll DP[10000] = {};
    for (auto &p : v) {
        ll A = p.first;
        ll B = p.second;
        for (int i = T - 1; i >= 0; i--) {
            DP[i + A] = max(DP[i + A], DP[i] + B);
        }
    }
    cout << *max_element(DP, DP + 10000) << endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

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

int main(void)
{
	bool judge = true;
	string s;
	cin >> s;
	for (int i = 1; i <= s.size(); i++)
	{
		if(i % 2 == 0)
		{
			if (s[i - 1] != 'L' && s[i - 1] != 'U' && s[i - 1] != 'D')
			{
				judge = false;
				break;
			}
		}
		else
		{
			if (s[i - 1] != 'R' && s[i - 1] != 'U' && s[i - 1] != 'D')
			{
				judge = false;
				break;
			}
		}
	}
	if (judge) { cout << "Yes" << endl; }
	else { cout << "No" << endl; }
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  ll n = 0;
  cin >> n;
  map<ll,ll> a;
  for(int i = 0;i < n;i++){
    ll in;
    cin >> in;
    a[in]++;
  }
  cout << a.size() << endl;
}

Measured memory_bytes: 3580
//GhostCai is huger than wjmzbmr
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1005;
struct Edge{
	int to,nxt;
}e[N<<1];
int n,x[N],head[N],ecnt,f[N],g[2][5005];
void add(int bg,int ed){e[++ecnt].nxt=head[bg];e[ecnt].to=ed;head[bg]=ecnt;}
void dfs(int u) {
	for(int i=head[u];i;i=e[i].nxt) dfs(e[i].to);
	memset(g[0],0x3f,sizeof g[0]);
	int cur=0;
	g[cur][0]=0;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;cur^=1;
		memset(g[cur],0x3f,sizeof g[cur]);
		for(int j=0;j<=x[u];j++) {
			if(j-x[v]>=0) g[cur][j]=min(g[cur^1][j-x[v]]+f[v],g[cur][j]);
			if(j-f[v]>=0) g[cur][j]=min(g[cur^1][j-f[v]]+x[v],g[cur][j]);
		}		
	}
	for(int i=0;i<=x[u];i++) f[u]=min(f[u],g[cur][i]);
}
int main() {
	cin>>n;
	for(int i=2,p;i<=n;i++) scanf("%d",&p),add(p,i);
	for(int i=1;i<=n;i++) scanf("%d",&x[i]);
	memset(f,0x3f,sizeof f);
	dfs(1);
	if(f[1]<0x3f3f3f3f) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
//#define int long long

using namespace std;
using LL = long long;
using P = pair<int, int>;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e18;
const int MOD = (int)1e9 + 7;

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

    int h, w, n;
    cin >> h >> w >> n;
    vector<int> a(n);
    REP(i, n) cin >> a[i];

    vector<vector<int>> ans(h, vector<int>(w, 0));
    int index = 0;
    REP(i, h) REP(j, w){
        if(i % 2 == 0){
            ans[i][j] = index + 1;
        }else{
            ans[i][w - j - 1] = index + 1;
        }
        a[index]--;
        if(a[index] <= 0){
            index++;
        }
    }
    REP(i, h) REP(j, w){
        cout << ans[i][j] << " \n"[j == w-1];
    }
}

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

#define PB push_back
#define ALL(x) (x).begin(),(x).end()

using namespace std;

void init();
int rec(int x);

int n;
vector<int> opt, memo;
const int inf = 1 << 25;

int main()
{
	init();

	cout << rec(n) << endl;
}

void init()
{
	cin >> n;

	memo.resize(n + 1, inf);
	memo[0] = 0;

	int x = 1;
	opt.PB(x);

	x = 6;
	while (x <= n)
	{
		opt.PB(x);
		x *= 6;
	}

	x = 9;
	while (x <= n)
	{
		opt.PB(x);
		x *= 9;
	}

	sort(ALL(opt), greater<>());
}

int rec(int x)
{
	if (memo[x] < inf)
		return memo[x];

	int ret = inf;

	for (int y : opt)
		if (x >= y)
			ret = min(ret, 1 +rec(x - y));

	return memo[x] = ret;
}


Measured memory_bytes: 640
class dice:
    def __init__(self, pip):
        self.pip = pip
        
    def move(self,dir):
        if str(dir) == "E":
            self.pip[0],self.pip[2],self.pip[3],self.pip[5] = self.pip[3],self.pip[0],self.pip[5],self.pip[2]
        elif str(dir) == "W":
            self.pip[0],self.pip[2],self.pip[3],self.pip[5] = self.pip[2],self.pip[5],self.pip[0],self.pip[3]
        elif str(dir) == "N":
            self.pip[0],self.pip[1],self.pip[4],self.pip[5] = self.pip[1],self.pip[5],self.pip[0],self.pip[4]
        elif str(dir) == "S":
            self.pip[0],self.pip[1],self.pip[4],self.pip[5] = self.pip[4],self.pip[0],self.pip[5],self.pip[1]

d = dice(list(map(int,input().split())))
inp = list(input())

for dir in inp:
    d.move(dir)

print(d.pip[0])



Measured memory_bytes: 5612
while True:
    m,f,r = map(int, input().split())
    if (m, f, r) == (-1, -1, -1):
        break
    if m == -1 or f == -1 or (m+f) < 30:
        print('F')
    elif (m+f) >= 80:
        print('A')
    elif 80 > (m+f) >= 65:
        print('B')
    elif 65 > (m+f) >= 50:
        print('C')
    elif 50 > (m+f) >= 30:
        if r >= 50:
            print('C')
        else:
            print('D')


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

vector<pair<long long, long long>> pri_check(long long N)
{
    vector<pair<long long, long long>> prime_fac;
    for (long long A = 2; A * A < N; A++)
    {
        if (N % A != 0)
            continue;

        long long exp = 0;

        while (N % A == 0)
        {
            exp++;
            N /= A;
        }

        prime_fac.push_back({A, exp});
    }

    if (N != 1)
        prime_fac.push_back({N, 1});

    return prime_fac;
}

//N=p_1^e_1*p_2^e_2...とおける。
//底は素因数にあたるので、指数の数を数えていけばいい。
void solve(long long N)
{
    vector<pair<long long, long long>> prime_fac = pri_check(N);
    long long cnt = 0;

    for (auto s : prime_fac)
    {
        for (int i = 1; i <= s.second; i++)
        {
            cnt++;
            s.second -= i;
        }
    }

    cout << cnt << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long N;
    scanf("%lld", &N);
    solve(N);
    return 0;
}


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

bool legal(string s){
    stack<int> st;
    for(char c: s){
        if(c == '(') st.push(1);
        else{
            if(st.empty()) return false;
            else st.pop();
        }
    }

    if(st.empty()) return true;
    else return false;
}

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    int st = 0;
    int st_ne = 0;
    for(char c: s){
        if(c == '(') ++st;
        else{
            if(st > 0) --st;
            else ++st_ne;
        }
    }



    string res = s;
    rep(i, st_ne) res = '(' + res;
    rep(i, st) res += ')';

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

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

    string s[n];
    int a[n];
    rep(i,n){
        cin >> s[i] >> a[i];
    }

    string t;
    cin >> t;

    int now = 0;
    rep(i,n){
        if(s[i] == t)now = i;
    }

    int ans = 0;

    srep(i,now + 1, n){
        ans += a[i];
    }

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


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        String ans=" ";
        if(A.length()>B.length()) ans = "GREATER";
        else if(A.length()<B.length()) ans = "LESS";
        else{
            for(int i=0;i<A.length();i++){
                int a = A.charAt(i);
                int b = B.charAt(i);
                if(a!=b){
                    ans = a>b?"GREATER":"LESS";
                    System.out.println(ans);
                    System.exit(0);
                }
                ans = "EQUAL";
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21332
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int N, K, x;
	int ans = 0;

	cin >> N >> K;

	for (int i = 0; i < N; i++)
	{
		cin >> x;

		ans += min(x, abs(K - x)) * 2;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
N,X = map(int,input().split())
l = []
bo = 0
for a in range(N+1):
    for b in range(N-a+1):
        if a*10000 + b*5000 + (N-a-b)*1000 == X:
            T = [a,b,N-a-b]
            bo+=1
            break


if bo==0:
    print('-1 -1 -1')
else:print(*T,sep=' ')

Measured memory_bytes: 9104
import sys
sys.setrecursionlimit(10**9)

def dfs(v):
    used[v] = True
    for _v in adjl[v]:
        if not used[_v]:
            dfs(_v)

n, m = map(int, input().split())
adjl = [[] for v in range(n + m)]
for i in range(n):
    kl = list(map(int, input().split()))
    k = kl[0]
    llist = kl[1:]
    for l in llist:
        adjl[i].append(l + n - 1)
        adjl[l + n - 1].append(i)

used = [False] * (n + m)
dfs(0)

if all(used[:n]):
  print('YES')
else:
  print('NO')


Measured memory_bytes: 37680
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
dp = [[0]*(1<<n) for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
  for bit in range(1<<n):
    if not dp[i][bit]: continue
    for k in range(n):
      if not (bit & 1<<k)  and A[i][k]:
        dp[i+1][bit|1<<k] += dp[i][bit]
        dp[i+1][bit|1<<k] %= mod
print(dp[n][(1<<n)-1])

Measured memory_bytes: 394904
import sys
input = sys.stdin.readline
import itertools

n = int(input())
a=tuple(map(int,input().split()))
b=tuple(map(int,input().split()))
l = list(itertools.permutations(sorted(a)))
res1=0
res2=0
for i in range(len(l)):
    if l[i]==a:
        res1=i
    if l[i]==b:
        res2=i
print(abs(res1-res2))


Measured memory_bytes: 8052
#include<stdio.h>
#define NMAX 100

int count = 0;

void selectionSort(int[], int);
void output(int[], int);

int main(){

  int N, i, j;
  int A[NMAX];

  scanf("%d", &N);
  
  for(i = 0; i < N; i++)
    scanf("%d", &A[i]);

  selectionSort(A, N);
  output(A, N);
  
  return 0;
}

void selectionSort(int A[], int N){

  int i, j, tmp, minj;
  
  for(i = 0; i <= N - 1; i++){
    
    minj = i;
    
    for(j = i; j <= N - 1; j++){
      
      if(A[j] < A[minj]){
	
	minj = j;
      }
    }
    
    tmp = A[i];
    A[i] = A[minj];
    A[minj] = tmp;
      
    if(A[i] < A[minj])count++;
  }
}
  

void output(int A[], int N){

  int i;

  for(i = 0; i < N; i++){
    if(i > 0) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n%d\n", count);
}
  



Measured memory_bytes: 2144
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(2*n);
    for (int & L : a)
        cin >> L;
    sort(begin(a),end(a));
    int ans = 0;
    for (int i = 0; i < n; ++i)
        ans += a[i*2];
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
    int n,k,a[105];
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int g=k/2,sum=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]<=g) sum+=a[i];
        else if(a[i]<=k)sum+=k-a[i];
        else sum+=a[i]-k;
    }
    cout<<sum*2<<endl;
    return 0;
}


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

int main(){
  int N;
  int p = 0;
  cin >> N;
  for(int i = 0; i < N; i++){
    string check;
    cin >> check;
    if(check == "Y"){
      p++;
    }
     
  }
    
  if (p >0){
    cout << "Four" << endl;
  }
  else if (p == 0){
    cout << "Three" << endl;
  }
}
       
      

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

int main(){
    ll n, m;
    cin >> n >> m;
    ll a, b;
    vll c(n, 0);
    REP(i, m){
        cin >> a >> b;
        a--;
        b--;
        c[a]++;
        c[b]++;
    }
    REP(i, n) cout << c[i] << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=200003;
int n,a[maxn];
bool b[maxn];
#define v(i) (a[i]>=x)
bool check(int x){
	int mid=(n+1)>>1,ans=maxn,ret=-1;
	for(int i=1,j=1;i<=n;i++){
		for(;j<=n&&v(i)==v(j);j++);
		if(i+1==j)continue;
		int tmp=min(abs(mid-i),abs(j-1-mid));
		if(tmp<ans)ans=tmp,ret=v(i);
	}
	return ~ret?ret:v(1);
}
int main(){
	scanf("%d",&n);
	n=(n<<1)-1;
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	int l=1,r=n,mid,ans=-1;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1024
import collections

N, K = map(int, input().split())
alist = collections.Counter(map(int, input().split()))
number = max(0,len(alist) - K )
answer = 0
if number == 0:
    print(0)
else:
    for a in alist.most_common()[-number:]:
        answer += a[1]
    print(answer)


Measured memory_bytes: 41500