akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> graph[n + 1];
    for (int l, r, c; cin >> l >> r >> c; ) {
        graph[l].emplace_back(r, c);
    }
    unsigned long long dist[n + 1];
    for (int i = 1; i <= n; i++) {
        graph[i].emplace_back(i - 1, 0);
        dist[i] = -1;
    }
    dist[1] = 0;
    set<pair<unsigned long long, int>> set;
    set.emplace(0, 1);
    do {
        auto current = set.begin()->second;
        set.erase(set.begin());
        for (auto& p : graph[current]) {
            if (dist[p.first] > dist[current] + p.second) {
                set.erase({dist[p.first], p.first});
                dist[p.first] = dist[current] + p.second;
                set.emplace(dist[p.first], p.first);
            }
        }
    } while (!set.empty());
    cout << (long long)dist[n];
    return 0;
}


Measured memory_bytes: 8704
#include "bits/stdc++.h" // {{{
using namespace std;
#define val         const auto
#define eb          emplace_back
#define emp         emplace
#define fi          first
#define se          second
#define X           first
#define Y           second
#define outl(x)     cout << (x) << '\n'
#define rep(i,n)    for(int i=0; i < (int)(n); ++i)
#define ALL(x)      begin(x), end(x)
#define TMPLT(T,U)  template<class T, class U>
#define ten(p)      ((long long)(1e##p))
#define FILL(a,v)   memset((a), (v), sizeof(a))
#define FAST()      ios::sync_with_stdio(false), cin.tie(nullptr)
#ifndef DEBUG
#define debug(...)
#define show(x)
#define show2(x,y)
#define LN()
#endif
typedef long long ll;
typedef pair<int,int> pii;
namespace ydk{
TMPLT(T,U) inline bool chmax(T &a, U b){return b>a ? a=b,1 : 0;}
TMPLT(T,U) inline bool chmin(T &a, U b){return b<a ? a=b,1 : 0;}
TMPLT(T,U) inline constexpr common_type_t<T,U> gcd(T x, U y)
{ return (x<y)? gcd(y,x) : (y <= 0)? x : gcd(y, x % y); }
TMPLT(T,U) inline constexpr ll lcm(T x, U y) { return (ll)x/gcd(x,y) * y; }
constexpr int INF   = 0x3f3f3f3f;
constexpr ll LINF   = 0x3f3f3f3f3f3f3f3fLL;
// }}}

constexpr int MX = 2 * ten(5) + 10;

void Xx_main_xX()
{
    int N;
    int a[MX];

    FAST();
    cin >> N;
    rep(i, N) cin >> a[i];

    int r = 0;
    ll ans = 0;
    int sum = 0;

    rep(l, N) {
        while(r < N && (sum ^ a[r]) == (sum + a[r])) sum ^= a[r++];
        ans += (r - l);
        (r == l)? ++r : sum ^= a[l];
    }
    outl(ans);
    return;
}

} // {{{

signed main(){cout << fixed << setprecision(9); ydk::Xx_main_xX(); return 0;} // }}}



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

using ll = long long;

#define pb push_back
#define mkp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define clr(a, b) memset(a, b, sizeof(a))
#define REP(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
#define REPD(i, a, b) for(int i=(int)(a)-1; i>=(int)(b); --i)
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll x; cin >> x;
    ll p = 100;
    int res = 0;
    while(x > p) {
    	p += p/100;  
    	++res;
    }
    cout << res << "\n";
    return 0;
}


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

using namespace std;
#define ll long long
#define mod 1000000007

vector<vector<int>> v;
int dp[100001][3];

int f(int i, int j) {
    if (i == v.size()) return 0;

    if (dp[i][j] != -1) return dp[i][j];

    int ans = INT_MIN;
    for (int k = 0; k < 3; k++) {
        if (k != j) {
            ans = max(ans, v[i][k] + f(i + 1, k));
        }
    }
    dp[i][j] = ans;
    return ans;
}

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

    memset(dp, -1, sizeof(dp));
    int n;
    cin >> n;

    v.resize(n);
    for (auto &i : v) {
        i.resize(3);
    }

    for (int i = 0; i < n; i++) {
        cin >> v[i][0] >> v[i][1] >> v[i][2];
    }
    cout << max(f(0, 0), max(f(0, 1), f(0, 2))) << "\n";
}


Measured memory_bytes: 19200
#include <stdio.h>
#include <stdlib.h>
 
int A[101][101];
int B[101];
int len;
 
void Maxchain_m(){
  int j,x,k,i,l;
  for(i=1;i<=len;i++){
    A[i][i]=0;
  }
  for(j=2;j<=len;j++){
    for(i=1; i<=len-j+1; i++){
      l = i + j - 1;
      A[i][l] = 200000;
      for(k=i; k<=l-1; k++){
	x = A[i][k] + A[k+1][l] + B[i-1] * B[k] * B[l];
	if(A[i][l] > x){
	  A[i][l] = x;
	}
      }
    } 
  }
}
 
main(){
  int m,i;
  scanf("%d",&len);
  for(i=1;i<=len;i++){
    scanf("%d%d", &m,&B[i]);
    if(i==1){
      B[0]=m;
    }  
  }
  Maxchain_m();
  printf("%d\n",A[1][len]);
  return 0;
}

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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<llong, llong>;

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

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	llong m, f, b;
	cin >> m >> f >> b;

	if(m+f < b)
		cout << "NA" << endl;
	else
		cout << (m>=b ? 0 : b-m) << endl;

	return 0;
}


Measured memory_bytes: 3096
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const ll MOD =998244353;
const ll hell=1000000007;
const int INF = 1e17;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

const int N=200005;
int A[11];int m;
int n,q;
int a[51],b[51],c[51],d[51];
int ans=0;
void cal()
{
    int cost=0;
    for(int i=0;i<q;i++)
    {
        if(A[b[i]]-A[a[i]]==c[i])
            cost+=d[i];
    }
    ans=max(ans,cost);
    
}
void recur(int i)
{
    if(i==n+1)
    {
        cal();
        return;
    }
    for(int j=A[i-1];j<=m;j++)
    {
        A[i]=j;
        recur(i+1);
    }
    
    
}

void solve()
{
    cin>>n>>m>>q;
    for(int i=0;i<q;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }
    A[0]=1;
    recur(1);
    cout<<ans<<endl;
    
}

int32_t main()
{
    IOS;
   // FILE *fin = freopen("in.txt","r",stdin);
    //FILE *fout = freopen("out.txt","w",stdout);

    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        
        solve();
    }
    return 0;
}


Measured memory_bytes: 3660
N = int(input())
S = list(input())

num_r = S.count('R')
num_g = S.count('G')
num_b = S.count('B')

ans = num_r * num_g * num_b

for i in range(0, N) :
  for temp in range(1, int((N-i+1)/2)) :
    j = i + temp
    k = i + 2 * temp
    c1 = S[i]
    c2 = S[j]
    c3 = S[k]
    if((c1 != c2) and (c2 != c3) and (c3 != c1)) :
      ans -= 1
        
        
print(ans)

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long


#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)

const int N=1e5+5;
const int mod=1e9+7;

int32_t main() {
string a,b;
cin>>a>>b;
if(a.size()>b.size())cout<<"GREATER";
else if(a.size()<b.size())cout<<"LESS";
else {

   int ok=2;
    for (int i = 0; i <a.size()  ; ++i) {
        if(a[i]<b[i]){return cout<<"LESS",0;}
        if(a[i]>b[i]){ok=1;break;}
    }
    if(ok==2)cout<<"EQUAL";
    else cout<<"GREATER";
}
}

Measured memory_bytes: 256
N,K = map(int,input().split())
S = input()
ans = 0
c = 0
s = ''
for i in range(N):
    if S[i] != s:
        c += 1
        s = S[i]
    else:
        ans += 1

while K > 0 and c > 1:
    if c >= 3:
        K -= 1
        c -= 2
        ans += 2
    else:
        K -= 1
        c -= 1
        ans += 1

print(ans)

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

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

using ll = long long;
using P = pair<ll,ll>;
using graph = vector<vector<int>>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int N;
  cin>>N;
  vector<int> v(N);
  rep(i,N) cin>>v[i];
  int ans = 0;
  rep(i,N-2){
    if((v[i]>v[i+1]&&v[i+1]>v[i+2])||(v[i]<v[i+1]&&v[i+1]<v[i+2])) ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007
#define MINP 0x00FF

// fact(n)
int fact(int n){
	if(n == 1)	return 1;
	else return (n * fact(n - 1));
}

// nCr(n,r)
int nCr(int n, int r){
	if(r == 0 || r == n)	return 1;
	else if(r == 1)	return n;
	return (nCr(n - 1, r - 1) + nCr(n - 1, r));
}

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

// lcm(a,b)
int lcm(int a,int b){
	return (a * b) / gcd(a,b);
}

// swap(&a, &b);
void swap(int *a,int *b){
	int tmp;
	tmp = *a;	*a = *b;	*b = tmp;
	return;
}

// qsort(array, size, sizeof(int),comp);
int comp(const int *a,const int *b){
	return (*a - *b);
}

// append(array,*size,addNum)
void append(int *array,int *size,int num){
	realloc(array, sizeof(int) * (*size + 1));
	array[(*size)] = num;
	++(*size);
}

// pop(array,*size) & nongetpop(array,*size)
int pop(int *array,int *size){
	int temp = array[(*size - 1)];
	nongetpop(array,&(*size));
	return temp;
}

int nongetpop(int *array,int *size){
	realloc(array,sizeof(int) * (*size - 1));
	--(*size);
}

int main(int argc, char const *argv[])
{
	int n,h[107];
	int l = 0,r;
	int cnt = 0,min = MINP,flag = 1;
	scanf("%d",&n);
	for (int i = 0; i < n; ++i)	scanf("%d",&h[i]);
	while(l < n){
		min = MINP;
		flag = 1;
		if(h[l] == 0){
			++l;
			continue;
		}
		for (int i = l; (i < n && flag); ++i)
		{
			for (r = l; r < n; ++r)
			{
				if(h[r] == 0){
					flag = 0;
					break;
				}
			}
		}
		for (int i = l; i < r; ++i)
		{
			if(min > h[i])	min = h[i];
		}
		for (int i = l; i < r; ++i)	h[i] -= min;
		cnt += min;
	}
	printf("%d\n", cnt);
}


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

using namespace std;

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

const int N = 100010;
const double eps = 1e-6;

int n, k;
int a[N];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + n);

    int l = 1, r = k, res = 0x3f3f3f3f;
    while(r <= n)
    {
        res = min(res, a[r] - a[l]);
        r++, l++;
    }

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


Measured memory_bytes: 640
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pre = a[0]
ans = 0
for i in range(n):
        if pre + a[i+1]-b[i] < 0:
                ans += pre + a[i+1]
                pre = 0
        elif 0<= pre + a[i+1]-b[i] <= a[i+1]:
                ans += b[i]
                pre = pre + a[i+1]-b[i]
        else:
                ans += b[i]
                pre = a[i+1]
print(ans)

Measured memory_bytes: 73444
#include <stdio.h>
#include <stdlib.h>

/*
  * 戦略
  * 左端から調査する。
  * 下がり始める地点を起点として記録
  * 同じ高さの地点が表われたら、そこまでで1チャンクである
  *  水面が初期高さなので、各セグメントごとに深さと底面の状態に応じて足し込んでいく
  * 同じ高さの地点がなければ、最も高かった頂点(もしくは台地の左端)を中点とする
  *  起点から最も近い中点と同じ高さの地点を新たな起点として、1チャンクを算出する
  * 1チャンクの算出後、中点以降の下がり始める点を起点としてくり返す
  * 頂点もしくは台地の左端が表れなければ、それ以降にチャンクがないので終了
  *
  * 左から順に調べればいいので各データはキューとして扱う
  * セグメントを調べるとき、左端にいると考える。
  *  高さPからval=-1なら水面Hに対してH-P+0.5、val=0ならH-P、val=1ならH-P-0.5の水量となる
  *  水量は2倍値を持っておく(1マス=2)。
 */

#define H_MIN -200000

#ifdef DEBUG
#define  DPRINT printf
#else
#define DPRINT(...)
#endif

struct q {
	int val;
	struct q *next;
};

struct q *
chunk(struct q *from, struct q *to)
{
	struct q *res = (struct q *)malloc(sizeof(struct q));
	struct q *arg;
	int h = 0;

	if (res == NULL)
		return NULL;

	res->next = NULL;
	res->val = 0;

	for (arg = from; arg != NULL; arg = arg->next) {
		res->val -= h * 2 + arg->val;
		h += arg->val;
		if (arg == to)
			break;
	}

	return res;
}

int
main(void)
{
	struct q *head = NULL;
	struct q *tail = NULL;
	struct q *res_h = NULL;
	struct q *res_t = NULL;
	struct q *qm;
	int h0 = 0, h1= 0;
	int sum = 0;
	int n = 0;
	int hm;
	char c;

	while (scanf("%c", &c) != EOF) {
		struct q *a = (struct q *)malloc(sizeof(struct q));

		if (a == NULL)
			return 1;

		a->val = (c == '/') ? 1 : (c == '_') ? 0 : -1;
		a->next = NULL;

		if (head == NULL) {
			head = tail = a;
		} else {
			tail->next = a;
			tail = a;
		}
	}

	while (head != NULL) { /* チャンクを見つける */
		struct q *a;

		/* 起点 */
		for (;head != NULL; head = head->next) {
			if (head->val == -1)
				break;
		}
		if (head == NULL)
			break;

		h0 = h1= 0;
		hm = H_MIN;
		qm = NULL;
		/* 起点の高さを探索 */
		for (a = head; a != NULL; a = a->next) {
			h1 += a->val;
			if (h0 == h1)
				break;
			if (a->val == 1 && h1 > hm) {
				hm = h1;
				qm = a;
			}
		}
		DPRINT("h0=%d h1=%d\n", h0, h1);
		/* 起点の高さがない場合、次点を探索 */
		if (a == NULL) {
			if (qm == NULL)
				break;
			for (a = head; a != NULL; a = a->next) {
				if (h0 == hm)
					break;
				h0 += a->val;
			}
			head = a;
			a = qm;
		}
		/* チャンク */
		if (a != NULL) {
			struct q *v = chunk(head, a);

			if (v == NULL)
				return 1;

			sum += v->val;
			n++;
			if (res_h == NULL) {
				res_h = res_t = v;
			} else {
				res_t->next = v;
				res_t = v;
			}
		}

		head = a->next;
	}

	printf("%d\n%d", sum / 2, n);
	for (;res_h != NULL; res_h = res_h->next) {
		printf(" %d", res_h->val / 2, res_h->next == NULL ? "" : " ");
	}
	printf("\n");

	return 0;
}



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


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

ll lcm(ll a, ll b){
    return a * b / gcd(a,b);
}

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

    cout << lcm(a,b) << endl;
}

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

using namespace std;

#define sz(v)           ((int)((v).size()))
#define clr(v, d)       memset(v, d, sizeof(v))
#define rep(i, v)       for(int i=0; i<sz(v); ++i)
#define lp(i, n)        for(int i=0; i<(int)(n); ++i)
#define lpi(i, j, n)    for(int i=(j); i<(int)(n); ++i)
#define lpd(i, j, n)    for(int i=(j); i>=(int)(n); --i)
#define INF             1000000000

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;


void init()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

const int N = 1e6+6;
const int MOD = 1e9+7;

ll f[N];

void calcfact(){
	f[0] = f[1] = 1;
	lpi(i, 2, N-2){
		f[i] = (f[i-1] * i) % MOD;
	}
}
long long power(long long a , long long b){
    long long x = 1 , y = a;
    while(b > 0){
        if(b & 1){
            x = (x * y);
            if(x > MOD)
                x %= MOD;
        }

        y = y*y;
        if(y > MOD)
            y %= MOD;

        b >>= 1;
    }
    return x;
}
long long nCr(long long n , long long r){
    return (f[n] * power(f[r] * f[n-r] %MOD , MOD - 2))% MOD;
}

int main()
{
	init();
	calcfact();
	int x, y;
	cin >> x >> y;
	int xtwos = -1, xones = -1;
	lp(i, x + 1){
		if((x-i) % 2 == 1)
			continue;
		if(i*2 + (x-i)/2 == y){
			xtwos = (x-i)/2;
			xones = i;
			break;
		}
	}
	if(xones == -1){
		cout << 0;
		return 0;
	}

	cout << nCr(xtwos+xones, xones);
	return 0;
}

Measured memory_bytes: 8064
num = int(input())
r0 = int(input())
min_r = r0
r1 = int(input())
if r1 < r0:
    min_r = r1
max_r = r1 - r0
for i in range(2,num):
    r = int(input())
    if (r - min_r) > max_r:
        max_r = (r - min_r)
    if r < min_r:
        min_r = r
print(max_r)


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    vec a(n);
    rep(i, n) cin >> a[i];

    mat c(h, vec(w, -1));

    int cur = 0;

    rep(i, h) rep(j, w) {
        if (i % 2 == 0) c[i][j] = cur+1;
        else c[i][w-1-j] = cur+1;
        a[cur]--;
        if (a[cur] == 0) cur++;
    }

    rep(i, h) {
        rep(j, w) {
            if (j != 0) cout << " ";
            cout << c[i][j];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
 
using namespace std;
 
char s[1234567];
 
int main() {
  scanf("%s", s);
  int k;
  scanf("%d", &k);
  for (int i = 0; s[i]; i++) {
    if (s[i] != 'a') {
      int ops = 'z' - s[i] + 1;
      if (ops <= k) {
        k -= ops;
        s[i] = 'a';
      }
    }
  }
  int len = strlen(s);
  while (k--) {
    s[len - 1]++;
    if (s[len - 1] > 'z') {
      s[len - 1] = 'a';
    }
  }
  puts(s);
  return 0;
}

Measured memory_bytes: 384
import math
n,k = map(int,input().split())
sum_prob = 0

for i in range(1, n+1):
    count = math.ceil(math.log2(k/i))
    if i < k:
        sum_prob += (1/n) * (1/2)**count
    else:
        sum_prob += (1/n)
print(sum_prob)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<Z A,Z...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n,m,x;
  cin >> n >> m >> x;
  ll c[n],a[n][m];
  rep(i,n) {
    R c[i];
    rep(j,m) R a[i][j];
  }
  ll ans=MAXL;
  rep(t,1<<n) {
    ll s=0;
    ll d[m];
    mem(d);
    rep(i,n) {
      if(t&(1<<i)) {
        s+=c[i];
        rep(j,m) d[j]+=a[i][j];
      }
    }
    ll f=1;
    rep(i,m) {
      if(d[i]<x) f=0;
    }
    if(f) ans=min(ans,s);
  }
  if(ans==MAXL) ans=-1;
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 3644
// Problem : B - ss
// Contest : AtCoder - AtCoder Beginner Contest 066
// URL : https://atcoder.jp/contests/abc066/tasks/abc066_b
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}
bool check(string s)
{
	int n=size(s);
	if(n&1)return false;
	if(s.substr(0,n/2)==s.substr(n/2,n/2))return true;
	return false;
}
void solve()
{
string s;cin>>s;
s.pop_back();
while(!check(s))
{
	s.pop_back();
}
cout<<size(s);
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 3620
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int main()
{
	string s; cin >> s;
	int ret = 0;
	for(int i=1;i<s.size();i++){
		ret += (s[i-1] != s[i]);
	}
	cout << ret << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<cstdlib> 
#include<sstream>
#include<cstdio>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
#define me(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=1111122;
const int M=200005;
#define Ma 1000000000000000000
int main()
{
    long double a,b;
    cin>>a>>b;
    LL ans=a*b;
    printf("%lld",ans);
    //system("pause");
    return 0;
}







/*------------------我要ac，我要蓝名-------------------------------*/

Measured memory_bytes: 3236
#include<map>
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
#include<functional>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	while(1){
		string a;
		int L; cin>>a>>L;
		if(L==0) break;
		while(a.length()<L) a="0"+a;

		map<string,int> f;
		f[a]=0;
		for(int t=1;;t++){
			string a1=a,a2=a;
			sort(a1.begin(),a1.end());
			sort(a2.begin(),a2.end(),greater<char>());

			int b1,b2;
			sscanf(a1.c_str(),"%d",&b1);
			sscanf(a2.c_str(),"%d",&b2);

			char tmp[8]; sprintf(tmp,"%d",b2-b1);
			a=tmp;
			while(a.length()<L) a="0"+a;
			if(f.count(a)>0){
				cout<<f[a]<<' '<<b2-b1<<' '<<t-f[a]<<endl;
				break;
			}
			f[a]=t;
		}
	}

	return 0;
}

Measured memory_bytes: 0
def make_divisors(n):
    lower_divisors,upper_divisors=[],[]
    i=1
    while i*i<=n:
        if n%i==0:
            lower_divisors.append(i)
            if i!=n//i:
                upper_divisors.append(n//i)
        i+=1
    return lower_divisors+upper_divisors[::-1]
n,m=map(int,input().split())
array=make_divisors(m)
array.reverse()
for ele in array:
    if m//ele>=n:
        print(ele)
        exit()


Measured memory_bytes: 9120
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define N 200005
 

int mark[N*5];

int check(int n){
	int p = sqrt(n);
	int val=1;
	if(n==1)
		if(mark[n]>1)
			return 0;
		else
			return 1;
	if(mark[n]>1 || mark[1]>0)
		val=0;
		
	for(int i=2;i<=p;i++){
		if(n%i==0 && (mark[i]>0 || mark[n/i]>0))
			val=0;
	}

	return val;
}

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

	int a[N],n,i;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>a[i];
		mark[a[i]]++;
	}
	if(n==1){
		cout<<1<<endl;
		return 0;
	}
	int val,ans=0;
	for(i=1;i<=n;i++){
		val = check(a[i]);
		if(val){
			// cout<<a[i]<<endl;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 8252
#include<bits/stdc++.h>
using namespace std;
long long int mod=1000000007;
long long int dp[(1<<21)+1]={0};
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//	for(int p=1;p<=t;p++)
	{
		int n;
		cin >> n;
		int arr[n][n],i,j,k;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			cin >> arr[i][j];
		}
		dp[(1<<n)-1]=1;
		long long int max=1<<n,temp;
		for(i=max-1;i>=0;i--)
		{
			temp=i;
			k=0;
			while(temp)
			{
				k+=(temp&1);
				temp/=2;
			}
			for(j=0;j<n;j++)
			{
				if(arr[k][j]&&(!(i&(1<<j))))
				dp[i]=(dp[i]%mod+dp[i|(1<<j)]%mod)%mod;
			}
		}
		cout << dp[0] << "\n";
	}
	return 0;
}

Measured memory_bytes: 16640
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

long long gcd(long long a, long long b)
{
	if(b == 0)
		return a;

	return gcd(b, a%b);
}

long long lcm(long long a, long long b)
{
	long long ret = max(a, b) / gcd(a, b);
	ret *= min(a, b);

	return ret;
}

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

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

	sort(T.begin(), T.end());

	long long ret = 1;
	for(int i=0; i<N; i++)
		ret = lcm(ret, T[i]);

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pi 3.1415926535897932384626
using namespace std;
      
struct P{
  int x;
  long long y;
  /*bool operator < (const P &a )const{
    //if(y!=a.y)
    return y<a.y;
  };*/
};

int a,b,c,d,i,k,n,m,e,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
long long o[111][9];
int l[1];
long long j[1];

long long x,y,z,mod=1000000007;
//string r;
char r[3];

P u[1];
queue<P> q;
stack<int> s;
//set<int> s;
map<int,int> p;

vector<int> v;


bool as(P a,P b)
{
  //if(a.x!=b.x)
  //return a.x<b.x;
  return a.y>b.y;
}

long long f(int n,int m)
{
  if(n==0)
  {
    //if(m<2)
    return 1;
    //return 0;
  }
  if(o[n][m]>=0) return o[n][m];
  if(m==2)
  {
    if(v[n]) return o[n][m]=(f(n-1,2)+f(n-1,0)*2)%mod;
    return o[n][m]=(f(n-1,2)+f(n-1,1)+f(n-1,0))%mod;
  }
  if(m)
  {
    if(v[n]) return o[n][m]=(f(n-1,2)+f(n-1,1))%mod;
    return o[n][m]=f(n-1,1);
  }
  return o[n][m]=f(n-1,0)*3%mod;
}

int main()
{
  memset(o,-1,sizeof(o));
  scanf("%lld",&x);
  v.push_back(0);
  for(;x;a++,x/=2)
    v.push_back(x%2);
  printf("%lld",f(a,1));
}
//0
//13




Measured memory_bytes: 384
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func read() string {
	sc.Scan()
	return sc.Text()
}

func geti() int {
	n, _ := strconv.Atoi(read())
	return n
}

// 10 11 12 => [10, 11, 12]
func getli(size int) ([]int64) {
	a := make([]int64, size)
	list := strings.Split(read(), " ")
	for i, s := range list {
		n, _ := strconv.ParseInt(s, 10, 64)
		a[i] = n
	}
	return a
}

func get2byte(size int) ([][]byte) {
	a := make([][]byte, size)
	for i := 0; i < size; i++ {
		var low string
		fmt.Scan(&low)
		a[i] = []byte(low)
	}
	return a
}

func transpose(a [][]int) {
	n := len(a)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			a[i][j], a[j][i] = a[j][i], a[i][j]
		}
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func main() {
	ab := getli(2)
	a := ab[0]
	b := ab[1]
	fmt.Println(solve(a, b))
}

func solve(a, b int64) int64 {
	if a % 2 == 0 && b % 2 == 0 {
		return b ^ (((b-a)/2)% 2)
	} else if  a % 2 == 0 && b % 2 == 1 {
		return ((b-a+1)/2)% 2
	} else if a % 2 == 1 && b % 2 == 0 {
		return a ^ b ^ (((b-a-1)/2)% 2)
	} else {
		return a ^ (((b-a)/2)% 2)
	}

}

Measured memory_bytes: 640
from functools import reduce
import math
import bisect

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    N_max = 100000
    l = []
    l.append(1)
    tmp = 1
    while tmp < N_max:
        tmp *= 6
        l.append(tmp)
    tmp = 1
    while tmp < N_max:
        tmp *= 9
        l.append(tmp)
    l.sort()
    d = [N_max for _ in range(N+1)]
    d[0] = 0
    for i in range(1,N+1):
        d[i] = d[i-1] + 1
        for j in range(len(l)):
            if i >= l[j]:
                d[i] = min(d[i],d[i-l[j]]+1)
    print(d[N])
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 4512
#include<iostream>
using namespace std;
int s[110][110]={0};
int main(){
    int w,h,n,x,y,a,i,j,k;
    cin >> w >> h >> n;
    for(i=0;i<n;i++){
    	cin >> x >> y >> a;
    	if(a==1){
    		for(j=0;j<x;j++){
    			for(k=0;k<h;k++){
    				s[j][k]=1;
    			}
    		}
    	}
    	else if(a==2){
    		for(j=x;j<w;j++){
    			for(k=0;k<h;k++){
    				s[j][k]=1;
    			}
    		}
    	}
    	else if(a==3){
    		for(j=0;j<w;j++){
    			for(k=0;k<y;k++){
    				s[j][k]=1;
    			}
    		}
    	}
    	else if(a==4){
    		for(j=0;j<w;j++){
    			for(k=y;k<h;k++){
    				s[j][k]=1;
    			}
    		}
    	}
    }
    x=0;
    for(i=0;i<w;i++){
    	for(j=0;j<h;j++){
    		if(s[i][j]==0)
    			x++;
    	}
    }
    cout << x << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
 
         
        public static void main(String[] args) throws java.io.IOException{
            Scanner scan = new Scanner(System.in);
            int [] r =new int[4];
            int [] l =new int[4];
            while(scan.hasNext()){
            float re =scan.nextFloat();
            float le =scan.nextFloat();
            if(re>=1.1)r[0]++;
            else if(re>=0.6&&re<1.1)r[1]++;
            else if(re>=0.2&&re<0.6)r[2]++;
            else r[3]++;
            if(le>=1.1)l[0]++;
            else if(le>=0.6&&le<1.1)l[1]++;
            else if(le>=0.2&&le<0.6)l[2]++;
            else l[3]++;
            }
            for(int i=0;i<4;i++)
            	System.out.println(r[i]+" "+l[i]);
        }
}

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

int main()
{
  int n, ans = 0, temp = 0;
  cin >> n;
  temp = n;
  for(int i=10; i<1000000; i*=10)
  {
    if(i==10 || i==1000 || i==100000)
    {
      if((n / i) == 0)
      {
        ans += n - (i / 10) + 1;
        break;
      }
      else
      {
        ans += i - (i / 10);
      }
    }
    else if((n / i) == 0)
    {
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3556
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int main()
{
    enum {SPADE, HEART, CLUB, DIAMOND};

    /* isCardExist[suit][rank]
     * suit 0: Spade, 1: Heart, 2: Club, 3: Diamond
     * rank = 1, 2, ..., 13 */
    constexpr int SUIT_NUM = 4;
    constexpr int RANK_NUM = 13;
    bool isCardExist[SUIT_NUM][RANK_NUM + 1] = {{false}};
    // unuse isCardExist[*][0]
    char suit;
    int rank;

    int cards_num;
    cin >> cards_num;
    while (cards_num--) {
        cin >> suit >> rank;
        switch (suit) {
            case 'S':
                isCardExist[SPADE][rank] = true;
                break;
            case 'H':
                isCardExist[HEART][rank] = true;
                break;
            case 'C':
                isCardExist[CLUB][rank] = true;
                break;
            case 'D':
                isCardExist[DIAMOND][rank] = true;
                break;
            default:
                printf("ERROR!\n");
                break;
        }
    }

    for (int i = 1; i <= 13; i++) {
        if (isCardExist[SPADE][i] == false) {
            cout << "S " << i << endl;
        }
    }
    for (int i = 1; i <= 13; i++) {
        if (isCardExist[HEART][i] == false) {
            cout << "H " << i << endl;
        }
    }
    for (int i = 1; i <= 13; i++) {
        if (isCardExist[CLUB][i] == false) {
            cout << "C " << i << endl;
        }
    }
    for (int i = 1; i <= 13; i++) {
        if (isCardExist[DIAMOND][i] == false) {
            cout << "D " << i << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
using namespace std;

#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 

#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846

const int N =1e5+5;

int mod= 1e9+7;
int dx[4]={0,0,+1,-1};
int dy[4]={+1,-1,0,0};

void solve(){

    int a,b;

	cin>>a>>b;
    int vt=1,ct=0;

	while(vt<b){
        ct++;
		vt+=(a-1);
	}

	cout<<ct<<endl; 
}

int32_t main() {
	cool;
	int t=1;
	//cin>>t;
	while(t--)
		solve();


	return 0;	  
}

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

#define ENDL '\n'
#define io ios_base::sync_with_stdio(false);cin.tie(0);
#define sayy cout<<"YES"<<ENDL;
#define sayn cout<<"NO"<<ENDL;

int main(){
    io

    int n;
    cin >> n;
    int x = (n*(n-1))/2;

    vector<int> v(n);
    for(int i(0); i<n; i++){
        cin >> v.at(i);
    }

    long long int result(0);
    for(int i(0); i<n; i++){
        for(int j(i+1); j<n; j++){
            result += v[i]*v[j];
        }
    }

    cout << result << ENDL;

    return 0;
}

Measured memory_bytes: 3624
#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>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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


int main() {

    int N;
    cin >> N;
    vector<string> vs(N);
    map<string, ll> m;
    REP(i, N) {
        cin >> vs[i];
        sort(vs[i].begin(), vs[i].end());
        if (m.find(vs[i]) == m.end()) m[vs[i]] = 1;
        else m[vs[i]]+=1;
    }   
    ll ans = 0;    
    for(auto tmp: m){
        ans += ((tmp.second - 1) * tmp.second) / 2;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 18176
import java.util.Scanner;

public class Main {

    String s;
    int n, k;

    public void solve() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        s = sc.next();

        String res = "";
        for (int i = 0; i < n; i++) {
            if (i == k-1) {
                res += Character.toLowerCase(s.charAt(i));
            } else {
                res += s.charAt(i);
            }

        }


        System.out.println(res);

    }
    public static void main(String[] args) {
        new Main().solve();

    }
}


Measured memory_bytes: 23636
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll k,a,b;
	cin>>k>>a>>b;
	if(b-a <= 2)
	{
		cout<<k+1<<"\n";
		return 0;
	}
	if(a-1 >= k)
	{
		cout<<(k+1)<<"\n";
		return 0;
	}
	k-=(a-1);
	ll x = a;
	ll z = k/2;
	x = a + z*(b-a);
	if(k%2)
		x++;
	cout<<x<<"\n";
	return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
#include <map>
using namespace std;

typedef long long ll;

map<ll, ll> M;
ll a[222222], p[222222];

int main(void)
{
	ll n, k, i, cnt = 0;

	scanf("%lld %lld", &n, &k);
	for (i = 1; i <= n; i++)
		scanf("%lld", &a[i]);

	++k;
	p[++cnt] = 1;
	M[1] = 1;

	ll turn = 0, rep = 0;
	while (1)
	{
		p[cnt + 1] = a[p[cnt]];
		++cnt;

		if (cnt == k)
		{
			printf("%lld", p[k]);
			return 0;
		}

		if (M[p[cnt]] == 0)
			M[p[cnt]] = cnt;
		else
		{
			ll v = M[p[cnt]];
			turn = v - 1, rep = cnt - v;
		}

		if (rep)
			break;
	}

	if (k <= turn)
		printf("%lld", p[k]);
	else
	{
		k -= turn;
		printf("%lld", p[turn + (k % rep == 0 ? rep : k % rep)]);
	}
	return 0;
}

Measured memory_bytes: 16140
import sys


def next_str() -> str:
    result = ""
    while True:
        tmp = sys.stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


def next_int() -> int:
    return int(next_str())


def main() -> None:
    n = next_int()
    s = [0]

    for i in range(n):
        a = next_int()
        s += [s[-1] + a]

    s.sort()
    ans = 0
    cnt = 0
    for i in range(1, len(s)):
        if s[i - 1] == s[i]:
            cnt += 1
        else:
            cnt = 0
        ans += cnt

    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 12620
#include <bits/stdc++.h>
using namespace std;
#define next next228

template<typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> &p) {
    out << "{" << p.first << ", " << p.second << "} ";//optional
    return out;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
    in >> p.first >> p.second;
    return in;
}

template<typename T>
istream &operator>>(istream &in, vector<T> &arr) {
    for (auto &i : arr)
        in >> i;
    return in;
}

template<typename T>
ostream &operator<<(ostream &out, vector<T> &arr) {
    for (auto i : arr)
        out << i << " ";//optional
    out << endl;
    return out;
}

typedef long long LL;
LL dp[110][2];
int n,p;
int main() {
    cin >> n >> p;
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (x & 1) {
            dp[i][0] = dp[i-1][1] + dp[i-1][0];
            dp[i][1] = dp[i-1][1] + dp[i-1][0];
        }
        else {
            dp[i][0] = dp[i-1][0] * 2ll;
            dp[i][1] = dp[i - 1][1] * 2LL;
        }
    }
    cout << dp[n][p] << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#define ld long double
#define ll long long int
#define ull unsigned long long int
#define rep(i,n) for(i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
using namespace std;
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 long LLINF=1LL<<60;
//set<int>::iterator it;
//|\_
//g++ -std=c++1z temp.cpp
//./a.out


int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
    int h,w,i,j;
    cin>>h>>w;
    vector<vector<char> > v(h+2,vector<char> (w+2,'%'));
    vector<vector<pair<int,int> > > ans(h+2,vector<pair<int,int> > (w+2,make_pair(0,0)));
    for(i=1;i<=h;i++){
        for(j=1;j<=w;j++)cin>>v[i][j];
    }
    for(i=1;i<=h;i++){//yoko
        for(j=1;j<=w;j++){
            if(v[i][j]=='#')continue;
            else{
                int sum=0;
                int t=0;
                while(v[i][j+t]=='.'){
                    sum++;
                    t++;
                }
                for(t=0;t<sum;t++){
                    ans[i][j+t].second=sum;
                }
                j+=sum;
            }
        }
    }
    for(i=1;i<=w;i++){//tate
        for(j=1;j<=h;j++){
            if(v[j][i]=='#')continue;
            else{
                int sum=0;
                int t=0;
                while(v[j+t][i]=='.'){
                    sum++;
                    t++;
                }
                for(t=0;t<sum;t++){
                    ans[j+t][i].first=sum;
                }
                j+=sum;
            }
        }
    }
    int maxans=0;
    for(i=1;i<=h;i++){
        for(j=1;j<=w;j++){
            maxans=max(maxans,ans[i][j].first+ans[i][j].second-1);
        }
    }
    fin(maxans);/*
    for(i=1;i<=h;i++){
        for(j=1;j<=w;j++){
            cout<<"("<<ans[i][j].first<<" "<<ans[i][j].second<<") ";
        }
        cout<<endl;
    }*/
//////////////////////////////////////////////////////
return 0;}







Measured memory_bytes: 35712
#include <stdio.h>
#include <limits.h>

int A[2000001];
int N = 0;

void upheap(int k)
{
    int v = A[k];
    A[0] = INT_MAX;

    while(v > A[k / 2]){
        A[k] = A[k / 2];
        k = k / 2;
    }

    A[k] = v;
}

void insert(int v)
{
    A[++N] = v;
    upheap(N);
}

void downheap(int k)
{
    int j, v;
    v = A[k];

    while(k <= N / 2){
        j = k + k;
        if(j < N && A[j] < A[j + 1])
            j++;
        if(v >= A[j])
            break;
        A[k] = A[j];
        k = j;
    }

    A[k] = v;
}

int extract(void)
{
    int v = A[1];
    A[1] = A[N--];
    downheap(1);

    return v;
}

int main(void)
{
    char buf[126];
    int v;

    while(1){
        scanf("%s", buf);

        if(buf[0] == 'i'){
            scanf("%d", &v);
            insert(v);
        }else if(buf[1] == 'x'){
            printf("%d\n", extract());
        }else{
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 4696
#include <stdio.h>

int main() {
  char in;
  int count=0;
  int max=0;
  while((in=getchar())!=EOF){
    if(in=='A'||in=='C'||in=='G'||in=='T') {
      count++;
    }else{
      max=(max<count)? count:max;
      count=0;
    }
  }
  printf("%d",max);
  return 0;
}

Measured memory_bytes: 128
n=int(input())
a=[int(input())for _ in range(n)]
if a[0]!=0:print(-1);exit()
for i in range(1,n):
  if a[i-1]+1<a[i]:print(-1);exit()
ans=0
for i in range(n-1,0,-1):
  if a[i]<=a[i-1]:ans+=a[i]
  else:ans+=1
print(ans)

Measured memory_bytes: 11052
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	if(a<b) cout<<"a < b"<<endl;
	if(a>b) cout<<"a > b"<<endl;
	if(a==b) cout<<"a == b"<<endl;
	return 0;
}


Measured memory_bytes: 3068
a,b = map(int, input().split())

if(a%2 == 1):
    a_h = (a+1)*100 // 8
    a_l = a*100 // 8 + 1
else:
    a_h = (a+1)*100 // 8 + 1  
    a_l = a*100 // 8
b_h = (b+1)*10
b_l = b*10

if(a_l >= b_h or b_l >= a_h):
    print(-1)
elif(a_l < b_l):
    print(b_l)
elif(b_l <= a_l):
    print(a_l)

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

int main() {
  int a, b, q;
  cin >> a >> b;
  q = (a * b) % 2;
  
  if (q == 1) {
    cout << "Odd" << endl;
  }
  else {
    cout << "Even" << endl;
  }
  
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

int N;

ld dp[310][310][310];

ld rec(int i, int j, int k) {
    if(dp[i][j][k] >= 0) return dp[i][j][k];
    if(i == 0 && j == 0 && k == 0) return 0.0;
    ld res = 0.0;
    if(i >= 1) res += i * rec(i - 1, j, k);
    if(j >= 1) res += j * rec(i + 1, j - 1, k);
    if(k >= 1) res += k * rec(i, j + 1, k - 1);
    res += N;
    res /= (i + j + k);
    return dp[i][j][k] = res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    cin >> N;
    int one = 0, two = 0, three = 0;
    rep(i, N) {
        int a; cin >> a;
        if(a == 1) one ++;
        else if(a == 2) two ++;
        else three ++;
    }
    rep(i, 310) rep(j, 310) rep(k, 310) dp[i][j][k] = -1;
    cout << fixed << setprecision(10) << rec(one, two, three) << endl;
	return 0;
}

Measured memory_bytes: 465792
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(){
 int N, result = 0;
 cin >> N;
  if(N % 10 == 9){
    N /= 10;
    result += 1;
  } else if(N % 10 == 1){
    N /= 10;
    result += 9;
  }
  if(N % 10 == 9){
    N /= 10;
    result += 10;
  } else if(N % 10 == 1){
    N /= 10;
    result += 90;
  }
  if(N % 10 == 9){
    N /= 10;
    result += 100;
  } else if(N % 10 == 1){
    N /= 10;
    result += 900;
  }
  cout << result << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
#include<sstream>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<list>
#include<map>
#include<vector>

using namespace std;


#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define MOD 1000000007

#define IMIN INT_MIN;
#define IMAX INT_MAX;


int main(){
    ll N, A, B;
    cin >> N >> A >> B;
    ll s = A+B;
    ll ans = N / s * A;
    ans += min(N%s, A);
    cout << ans << endl;



	return 0;
}


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

int main() {
    
    string alpha;
    cin >> alpha;
    
    if(islower(alpha[0])){
        cout << 'a' << endl;
    }else{
        cout << 'A' << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3592