akhauriyash/Code-Regression huggingface dataset:
/*
 * main.c
 *
 *  Created on: 2020/03/28
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a > b ? b : a)
typedef long long int ll;
typedef unsigned long long int ull;

int sort_inc(const void *a, const void *b) { return (*(int*)a - *(int*)b);}
int sort_dec(const void* a, const void* b) { return (*(int*)b - *(int*)a);}
int sort_dec_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = -1; }
    else if (da == db) { val = 0; }
    else { val = 1; }
    return val;
}
int sort_inc_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = 1; }
    else if (da == db) { val = 0; }
    else { val = -1; }
    return val;
}
int sort_dic(const void *a, const void *b) {
    char *pa = (char *)a;    char *pb = (char *)b;    int i = 0, val = 0, N = 10;
    for (i = 0; i < N; i++) {
    	char da = pa[i], db = pb[i];
    	if (da == db) continue;
  		if (da > db) val = 1; else val = -1;
        break;
    }
    return val;
}

void yesno(int ans) {
	if (ans == 1) {	printf("Yes\n");
	} else {		printf("No\n");	}
	return;
}

void okng(int ans) {
	if (ans == 1) { printf("OK\n");
	} else { 		printf("NG\n");	}
	return;
}

char S[1001] = {0};
char T[1001] = {0};
int match[1000] = {0};
int main()
{
	scanf("%s", S);
	scanf("%s", T);

	int i = 0;
	int len = strlen(S);
	int tlen = strlen(T);
	int match_max = 0;
	for (i = 0; i <= len-tlen; i++) {
		//printf("i=%d\n", i);
		int count = 0, j = 0;
		for (j = 0; j < tlen; j++) {
		//	printf("%c %c\n", S[i+j], T[j]);
			if (S[i+j] == T[j]) {
				count++;
			}
		}
		match_max = MAX(match_max, count);
	}

	int ans = tlen - match_max;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 1680
using System;
using System.Linq;

namespace kakomon
{
    class Program
    {
        static void Main(string[] args)
        {
            arc073_c();
        }

        static void arc073_c()
        {
            // C - Sentou
            long n;
            long t;
            long[] A;
            long[] nt = Console.ReadLine().Trim().Split().Select(long.Parse).ToArray();
            n = nt[0];
            t = nt[1];
            A = Console.ReadLine().Trim().Split().Select(long.Parse).ToArray();
            long st = 0;
            long ed = t;
            ulong ans = 0;
            for (long i=1; i<n; i++)
            {
                if (A[i] <= ed)
                {
                    // 次の人が間に合う
                    ed = A[i] + t;
                }
                else
                {
                    // 間に合わない(止まっている)
                    ans += (ulong)(ed - st);
                    st = A[i];
                    ed = A[i] + t;
                }
            }
            // ラスト1
            ans += (ulong)(ed - st);

            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 32416
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

int N;
int* marked_boss;

struct Node{
	bool isMarked;
	int marked_time;
};

struct Query{
	Query(int arg_query_time,int arg_value){
		query_time = arg_query_time;
		value = arg_value;
	}
	int query_time,value;
};

Node*info;

int get_marked_boss(int id,int query_time){

	if(info[id].isMarked == true && info[id].marked_time < query_time){
		return id;
	}else{
		return marked_boss[id] = get_marked_boss(marked_boss[id],query_time);
	}
}


int main(){

	int Q,value,tmp;
	char buf[2];
	ll ans;

	marked_boss = new int[100001];
	info = (Node*)malloc(sizeof(Node)*(100001));

	stack<Query> S;

	while(true){
		scanf("%d %d",&N,&Q);
		if(N == 0 && Q == 0)break;

		for(int i = 1; i <= N; i++){
			info[i].isMarked = false;
			info[i].marked_time = BIG_NUM;
		}

		marked_boss[1] = 1;
		info[1].isMarked = true;
		info[1].marked_time = 0;

		for(int i = 2; i <= N; i++){
			scanf("%d",&value);
			marked_boss[i] = value;
		}

		for(int time = 1; time <= Q; time++){

			scanf("%s %d",buf,&value);

			if(buf[0] == 'Q'){
				S.push(Query(time,value));
			}else{
				info[value].isMarked = true;
				info[value].marked_time = min(info[value].marked_time,time);
			}
		}

		ans = 0;

		while(!S.empty()){
			tmp = get_marked_boss(S.top().value,S.top().query_time);
			ans += tmp;
			S.pop();
		}

		printf("%lld\n",ans);
	}

	return 0;
}

Measured memory_bytes: 4100
def main():
    N = int(input())
    SP = [list(input().split()) for i in range(N)]
    for i, SPl in enumerate(SP):
        SPl.append(i+1)
        SPl[1] = int(SPl[1])
    # print(SP)
    SP.sort(reverse=True, key=lambda x: x[1])
    # print(SP)
    SP.sort(key=lambda x: x[0])
    # print(SP)

    for sp in SP:
        print(sp[2])


if __name__ == "__main__":
    main()


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


int main(void) {
  string n;
  cin >> n;
  for(int i=0; i<3; i++) {
    if (n[i] == '1') {
      n[i] = '9';
    } else if(n[i] == '9'){
      n[i] = '1';
    }
  }
  cout << n << endl;
}

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

const int N = 2005;
const int mod = 1e9 + 7;
const int half = 5e8 + 4;

int n;
int sz[N]; // number of edges
int prd[N];
int f[N][N][3]; // (i, j, k) subtree i, number of edges: j, number of edges connect to i: k
int g[N][N][3]; // knapsack
vector<int> G[N];

// a fixed set of edges has number of edges: i and number of components: j
// number of ways *= (2 ^ j) * (n - i)! * ((-1) ^ i)

void add(int &x, int y) {
	x = (x + y) >= mod ? (x + y - mod) : (x + y);
}

void dfs(int u) {
	for (auto v : G[u]) dfs(v);
	int id = 0;
	g[0][0][0] = 1;
	for (auto v : G[u]) {
		++id;
		// reset
		for (int i = 0; i <= sz[u] + sz[v] + 1; ++i) {
			for (int j = 0; j <= 2; ++j) g[id][i][j] = 0;
		}
		for (int i = 0; i <= sz[u]; ++i) {
			for (int j = 0; j <= sz[v]; ++j) {
				for (int k = 0; k <= 2; ++k) {
					// do not use u-v edge
					for (int l = 0; l <= 2; ++l) {
						add(g[id][i + j][k], 1LL * g[id - 1][i][k] * f[v][j][l] % mod); 
					}
					// use u-v edge
					if (k == 0) {
						add(g[id][i + j + 1][k + 1], 2LL * g[id - 1][i][k] * f[v][j][0] % mod);
						add(g[id][i + j + 1][k + 1], 1LL * g[id - 1][i][k] * f[v][j][1] % mod);
					}
					if (k == 1) {
						add(g[id][i + j + 1][k + 1], 1LL * g[id - 1][i][k] * f[v][j][0] % mod);
						add(g[id][i + j + 1][k + 1], 1LL * g[id - 1][i][k] * f[v][j][1] % mod * half % mod);
					}
				}
			}
		}
		sz[u] += sz[v] + 1;
	}
	// cout << "At " << u << '\n';
	for (int i = 0; i <= sz[u]; ++i) {
		for (int j = 0; j <= 2; ++j) {
			f[u][i][j] = g[id][i][j];
			// cout << f[u][i][j] << ' ' << i << ' ' << j << '\n';
 		}
 	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 2; i <= n; ++i) {
		int p; cin >> p, G[p].push_back(i);
	}
	dfs(1);
	prd[0] = 1; 
	for (int i = 1; i <= n; ++i) prd[i] = 1LL * prd[i - 1] * i % mod;
	int res = 0;
	for (int i = 0; i < n; ++i) {
		int tmp = 0;
		for (int j = 0; j <= 2; ++j) add(tmp, f[1][i][j]);
		// inclusion-exclusion
		if (i & 1) tmp = mod - tmp;
		add(res, 1LL * tmp * prd[n - i] % mod);
	}
	cout << res;
}

Measured memory_bytes: 93056
#include <iostream>
#include <set>
#include <algorithm>
#include <string>
#include <vector>
#define rep(i,a) for(int i=0;i<a;i++)
using namespace std;

int main(void){
	int n;
	int w,h,s,t;
	while(cin>>n,n){
		cin>>w>>h;
		vector<vector<int> > m(h,vector<int>(w));
		//cout<<w<<' '<<h<<endl;
		rep(i,n){
			int a,b;
			cin>>a>>b;
			--a,--b;
			m[b][a]++;
		}
		cin>>t>>s;
		/*
		cout<<w<<' '<<h<<endl;
		cout<<s<<' '<<t<<endl;
		cout<<h-s+1<<' '<<w-t+1<<endl;//*/
		//rep(i,h){rep(j,w)cout<<m[i][j];cout<<endl;}
		int ret = -1;
    rep(i,h-s+1){
      rep(j,w-t+1){
				int c = 0;
//				cout<<i<<' '<<j<<endl;
				rep(k,s)rep(l,t)if(m[i+k][j+l])c++;
				ret = max(c,ret);
			}
		}
		cout<<ret<<endl;
	}
}

Measured memory_bytes: 3096
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int MOD = 1e9+7;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> c(n);
  rep(i, n) cin >> c[i];
  vector<ll> dp(n+1);
  dp[0] = 1;
  vector<int> idx(2*1e5+1, -1);
  idx[c[0]] = 0;
  for (int i=1; i<=n; i++) {
    dp[i] = dp[i-1];
    if (idx[c[i]] >= 0 && c[i] != c[i-1])
      (dp[i] += dp[idx[c[i]]]) %= MOD;
    idx[c[i]] = i;
  }
  cout << dp[n] << endl;
  return 0;
}

Measured memory_bytes: 3456
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(void){
  int a, b, h;
  cin >> a;
  cin >> b;
  cin >> h;

  cout << (a+b)*h/2 << endl;
  return 0;
}


Measured memory_bytes: 256
from itertools import accumulate
n, k = map(int, input().split())
s = input()
a = []
cnt = 0
now = s[0]
for ss in s:
    if ss == now:
        cnt += 1
    else:
        a.append(cnt)
        cnt = 1
        now = ss
a.append(cnt)

a = [0]*(1-int(s[0])) + a + [0]*(1-int(s[-1]))
la = len(a)
kk = 2*k+1
if la == 1 or la <= kk:
    print(n)
    exit()
    
ac = [0] + list(accumulate(a))
ans = -float('inf')
for i in range(kk, la+1, 2):
    ans = max(ans, ac[i] - ac[i-kk])
print(ans)

Measured memory_bytes: 9308
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
L = list(map(int,input().split()))

maxL = max(L)

print("Yes" if sum(L)-maxL > maxL else "No")

Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <functional>
#include <iomanip>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

// #define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _fromto2(i,n) for(int i=0;i<=(n);++i)
#define _fromto3(i,a,b) for(int i=(a);i<=(b);++i)
#define fromto(...) _overload3(__VA_ARGS__,_fromto3,_fromto2,)(__VA_ARGS__)

#define rrep(i,n) for(int i=(n);i>=0;--i)
#define iter(it,v) for(auto it=v.begin();it!=v.end();++it)
const int MOD = 1e9+7;
const int INF = 1e9;
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; }

// debug
template<class T>ostream& operator<<(ostream& os, vector<T>& vec){os<<"{";for(int i=0;i<vec.size();++i)os<<(i?", ":"")<<vec[i];os<<"}";return os;}
template<class T1,class T2>ostream& operator<<(ostream& out,const pair<T1,T2>& rhs){out<<"("<<rhs.first<<", "<<rhs.second<<")";return out;}
#include<type_traits>
template<typename T,size_t SIZE,enable_if_t<!is_same<remove_cv_t<T>,char>::value,nullptr_t> = nullptr>ostream& operator<<(ostream& os,T(&arr)[SIZE]){os<<"{";for(size_t i=0;i<SIZE;++i)os<<(i?", ":"")<<arr[i];os<<"}";return os;}
#ifdef LOCAL
    #define debug(v) cerr<<v<<"\n"
#else
    #define debug(...) 42
#endif


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

  int ans = 0;
  rep(i, N-2) {
    if (S[i] == 'A' && S[i+1] == 'B' && S[i+2] == 'C') ++ans;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, x, y) for (ll i = x; i <= y; i++)
#define BIT(t) (1ll << t)
#define PER(i, y, x) for (ll i = y; i >= x; i--)
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define pll pair<ll, ll>
#define SIZE(v) ll(v.size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
//        ios::sync_with_stdio(false);
//        cin.tie(nullptr);

ll const MOD = 998244353;
ll mod_p(ll x, ll y) {
       x %= MOD;
       y %= MOD;
       return (x + y + MOD) % MOD;
}

ll mod_m(ll x, ll y) {
       x %= MOD;
       y %= MOD;
       return x * y%MOD;
}

ll mod_pow(ll x, ll t) {
       x %= MOD;
       if (t == 0) {
               return 1;
       }
       else {
               ll v = mod_pow(x, t / 2);
               if (t % 2 == 0) {
                       return v * v % MOD;
               }
               else {
                       return v * v%MOD * x %MOD;
               }
       }
}

ll mod_inv(ll x) {
       return mod_pow(x, MOD - 2);
}

int main(){
        ll n;
        cin >> n;
        vll a(n+1);
        ll t = -1;
        REP(i,1,n){
                ll x;
                cin >> x;
                a[x]++;
              if(i==1 && x != 0){
                      cout << 0 << endl;
                      return 0;
              }else if(i > 1 && x == 0){
                      cout << 0 << endl;
                      return 0;
              } 
              t = max(t, x);
        }
        ll ans = 1;
        REP(i,1,t){
                REP(j,1,a[i]){
                        ans = mod_m(ans, a[i-1]);
                }
        }
        cout << ans << endl;
}

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

using namespace std;

int main() {
    string S;
    string parts[4] = {"dream", "dreamer", "erase", "eraser"};

    cin >> S;
    reverse(S.begin(), S.end());
    for(int i = 0; i < 4; i++) reverse(parts[i].begin(), parts[i].end());

    bool can = true;
    int head = 0;
    while(1) {
        can = false;
        for(int p = 0; p < 4; p++) {
            if(parts[p] == S.substr(head, parts[p].size())) {
                head += parts[p].size();
                can = true;
                break;
            }
        }
        
        if(can == false) {
            cout << "NO" << endl;
            return 0;
        }

        if(head == S.size()) {
            cout << "YES" << endl;
            return 0;
        } else if (head > S.size()) {
            cout << "NO" << endl;
            return 0;
        }

    }

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

const long long INFLL = 1LL << 60;
const int INFI = 1000000000;


int main() {
    int A,B,C; cin >> A >> B >> C;
    string ans = "NO";
    for(int i=0;i<=B-1;i++){
        if(i*A%B == C)ans = "YES";
    }
    cout << ans << endl;
}


Measured memory_bytes: 3600
from collections import deque
mod=10**9+7
N,K=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)

rnk=[0 for i in range(N)]
reached=[0 for i in range(N)]
q=deque([0])
while(len(q)>0):
	r=q.popleft()
	reached[r]=1
	for p in G[r]:
		if reached[p]==1:
			continue
		rnk[p]=rnk[r]+1
		q.append(p)
#print(rnk)
reached=[0 for i in range(N)]
q=deque([0])
dp=[-1 for i in range(N)]
dp[0]=K
while(len(q)>0):
	r=q.popleft()
	reached[r]=1
	index=1
	if rnk[r]>0:
		index=2
	for p in G[r]:
		if reached[p]==1:
			continue
		dp[p]=K-index
		index+=1
		q.append(p)
#print(dp)
ans=1
for i in range(N):
	ans=ans*dp[i]
	ans%=mod
print(ans)


Measured memory_bytes: 76604
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#include<limits.h>
int main(){
    char S[102],T[102];
    scanf("%s",S);
    scanf("%s",T);
    char buf[102];
    strcpy(buf,S);
    for(int i=0;i<strlen(S);i++){
        char keep=buf[strlen(S)-1];
        for(int j=strlen(S)-1;j>0;j--)
           buf[j] = buf[j-1];
        buf[0] = keep;
        if(strcmp(buf,T)==0){
            printf("Yes");
            return 0;
        }
    }
    printf("No");
    return 0;
}


Measured memory_bytes: 1732
#include<stdio.h>

typedef struct{
  int id;
  int a;
  int time;
}T;
T Team[51],tmp;

int main()
{
  int i,j,M,T,P,R,m,t,p;
  int mis[51][11];
  while(1){
    scanf("%d%d%d%d",&M,&T,&P,&R);
    if(M==0&&T==0&&P==0&&R==0)break;
    for(i=1;i<51;i++){
      for(j=0;j<11;j++)mis[i][j]=0;
      Team[i].id=i;
      Team[i].a=0;
      Team[i].time=0;
    }
    for(i=0;i<R;i++){
      scanf("%d%d%d%d",&m,&t,&p,&j);
      if(j!=0)mis[t][p]++;
      else{
	Team[t].a++;
        Team[t].time+=(m+mis[t][p]*20);
      }
    }
    for(i=1;i<T+1;i++){
      for(j=T;j>i;j--){
	if(Team[j].a>Team[j-1].a){
	  tmp=Team[j];
	  Team[j]=Team[j-1];
	  Team[j-1]=tmp;
	}
	if(Team[j].a==Team[j-1].a &&Team[j].time<Team[j-1].time){
	  tmp=Team[j];
	  Team[j]=Team[j-1];
	  Team[j-1]=tmp;
	}	
	if(Team[j].a==Team[j-1].a &&Team[j].time==Team[j-1].time && Team[j].id>Team[j-1].id){
	  tmp=Team[j];
	  Team[j]=Team[j-1];
	  Team[j-1]=tmp;
	}
      }
    }
    printf("%d",Team[1].id);
    for(i=2;i<T+1;i++){
      if(Team[i].a==Team[i-1].a &&Team[i].time==Team[i-1].time)printf("=");
      else printf(",");
      printf("%d",Team[i].id);
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 608
#include<stdio.h>
int main()
{
	long long int i,N,A,B,sum=0,t;
	scanf("%lld %lld %lld",&N,&A,&B);
	sum = N/(A+B)*A;
	t = N%(A+B);
	if(t != 0)
	{
		if(t > A)
		{
			sum = sum+A;
		}
		else
		{
			sum = sum + t;
		}
	}
	printf("%lld",sum);
	
	
 } 

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

int main(){

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

    set<string> dict;
    bool rule = true;
    for(int i = 0; i < N - 1; i++){
        if(W[i].back() != W[i + 1].front()) rule = false;
        dict.insert(W[i]);
    }
    dict.insert(W.back());
    if(dict.size() != N) rule = false;

    if(rule) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
#include <complex>
 
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>
 
#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(int)(b);i<(int)(e);i++)
#define ALL(c) (c).begin(), (c).end()
#define EACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define RALL(c) (c).rbegin(), (c).rend()
#define ALLA(a,n) ((a)+0), ((a)+n)
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef vector<string> vstring;
typedef vector<double> vdouble;

template<class T>void pp(T v,int n){ REP(i,n)cout<<v[i]<<(i+1==n?'\n':' '); }
template<class T>void pp(T v){ EACH(it,v) cout<<(it==v.begin()?"":" ")<<*it; cout << endl;  }
template<class T>T& ls(T& a,T b){ if(b<a) a=b; return a; }
template<class T>T& gs(T& a,T b){ if(b>a) a=b; return a; }
inline ll to_i(const string& s){ll n;sscanf(s.c_str(),"%lld",&n);return n;}
inline string to_s(ll n){char buf[32];sprintf(buf,"%lld",n);return string(buf);}

inline void write_bool(bool b, const string &tval, const string &fval) {
  cout << (b ? tval : fval) << endl;
} 
inline void YESNO(bool b) { return write_bool(b, "YES", "NO"); }
inline void YesNo(bool b) { return write_bool(b, "Yes", "No"); }
inline void yesno(bool b) { return write_bool(b, "yes", "no"); }

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

ll solve(string &s, string &t) {
  vector<int> vs[26];
  REP(i,s.size()) {
    vs[s[i]-'a'].push_back(i);
  }

  ll result = 0;
  int cur = 0;
  REP(i,t.size()) {
    // cout << "t[i] = " << t[i] << ' ' << ", " << cur << ' ' << result << endl;
    int ch = t[i] - 'a';
    if (vs[ch].empty()) return -1;
    auto it = lower_bound(ALL(vs[ch]), cur);
    if (it != vs[ch].end()) {
      int pos = *it;
      result += pos - cur + 1;
      cur = pos + 1;
    } else {
      it = lower_bound(ALL(vs[ch]), 0);
      int pos = *it;
      result += s.length() - cur + pos + 1;
      cur = pos + 1;
    }
  }

  return result;
}

int main() {
  string s, t;
  while (cin >> s >> t) {
    cout << solve(s, t) << endl;
  }
}


Measured memory_bytes: 1148
#include <iostream>

using namespace std;
using ll = long long;

int c[500];
int s[500];
int f[500];

int main(){
    int n;

    cin >> n;

    for (int i = 0; i < n - 1; ++i) {
        cin >> c[i] >> s[i] >> f[i];
    }

    for (int from = 0; from < n - 1; ++from) {
        int t = 0;
        for (int to = from; to < n - 1; ++to) {
            if (t < s[to]) t = s[to];
            else if (t % f[to] != 0) t += f[to] - t % f[to];
            t += c[to];
            //cout << " - " << t << endl;
        }
        cout << t << endl;
    }
    cout << 0 << endl;
}

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

int calc(int x,int y,int z)
{
    return (x+y)*(x+y)+(z+y)*(z+y)+(x+z)*(x+z);
}

main()
{
    int n; cin>>n;
    vector<int> ans(n);
    for(int x=1; x*x<=n*2; x++)
    {
        for(int y=1; (x+y)*(x+y)<=2*n; ++y)
        {
            for(int z=1; ; z++)
            {
                int val=calc(x,y,z);
                if(val>2*n) break;
                ans[val/2-1]++;
            }
        }
    }
    for(int &x: ans) cout << x << "\n";
}

Measured memory_bytes: 3592
#include<iostream>
using namespace std;
int main(){
  int a[5], k;
  for(int i=0; i<5; i++){
    cin >> a[i];
  }
  cin >> k;
  cout << (a[4] - a[0] <= k ? "Yay!": ":(") << endl;
  return 0;
}

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

#if defined(DEBUG)

#include <unistd.h>
#include <sys/fcntl.h>
#define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
#define DCALL(func, ...) func(__VA_ARGS__)

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#else  // defined(DEBUG)

#define DLOG(...)
#define DCALL(func, ...)

#endif // defined(DEBUG)
// ----------------------------------------------------------------------

void showvec(auto v) {
  for (auto x : v) {
    cerr << x << " ";
  }
  cerr << endl;
}

// ----------------------------------------------------------------------
int main(int argc, char *argv[]) {
#if defined(DEBUG)
  // GDB on Cygwin ignores redirection at run command.
  if (argc == 2) dup2(open(argv[1], 0), 0);
#else
  // For performance.  We should not use C-style stdio functions
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cout << setprecision(20);

  int N;
  cin >> N;
  int K = 1 << N;
  vector<int> S(K);
  for (int i = 0; i < K; i++) cin >> S.at(i);
  sort(S.begin(), S.end(), greater<int>());
  vector<int> cur({S.at(0)});
  vector<bool> used(K);
  used.at(0) = true;

  for (int i = 0; i < N; i++) {
    DLOG("i = %d", i);
    DCALL(showvec, cur);
    vector<int> nxt;
    int idx = 0;
    for (int x : cur) {
      while (idx < K && (used.at(idx) || x == S.at(idx))) idx++;
      if (idx == K) {
	cout << "No\n";
	return 0;
      }
      used.at(idx) = true;
      nxt.push_back(x);
      nxt.push_back(S.at(idx));
    }
    cur = nxt;
    sort(cur.begin(), cur.end(), greater<int>());
  }
  cout << "Yes\n";
  return 0;
}


Measured memory_bytes: 4080
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VV = vector<VI>;
using VS = vector<string>;

// tourist set
template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << '\n'; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// tourist set end

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

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'
#define p2(s, t) cout << (s) << " " << (t) << '\n'
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << '\n'
#define p_yes() p("YES")
#define p_no() p("NO")
#define SZ(x) ((int)(x).size())
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(ALL(A), greater<ll>())

void no(){p_no(); exit(0);}
void yes(){p_yes(); exit(0);}

const ll mod = 1e9 + 7;
const ll inf = 1e18;
const double PI = acos(-1);

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

    // input
    string s; cin >> s;

    ll cnt = 0;
    for(char c : s){
      if(c=='1') cnt++;
    }
    p(cnt);
    
    return 0;
}

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

using namespace std;

// #define DEBUG 1
#define DFILE "t1.1"

int main() {
  int r, d, x, i;

#ifdef DEBUG
#define cin fin
  fstream fin(DFILE);
#endif

  cin >> r >> d >> x;
  for (i = 1; i <= 10; i++) {
    x = x * r - d;
    cout << x << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N=int(input())
    A=tupin()

    from collections import Counter
    c=Counter(A)
    total=0
    
    for t in c.items():
        ag,b=t
        total+=(b*(b-1))//2
    #print(total)
    for m in A:
        a=c[m]
        print(total-((a*(a-1))//2)+((a-1)*(a-2))//2)
#%%submit!
resolve()

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

int main() {
  int n, q;
  string s;
  cin >> n >> s >> q;
  vector<set<int>> is(26);
  rep(i,n) is[s[i]-'a'].insert(i);
  rep(qi,q) {
    int ty;
    cin >> ty;
    if (ty == 1) {
      int i; char c;
      cin >> i >> c;
      --i;
      is[s[i]-'a'].erase(i);
      s[i] = c;
      is[s[i]-'a'].insert(i);
    } else {
      int l, r;
      cin >> l >> r;
      --l;
      int ans = 0;
      rep(i,26) {
        auto it = is[i].lower_bound(l);
        if (it != is[i].end() && *it < r) ++ans;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}


Measured memory_bytes: 27248
#include<bits/stdc++.h>
using namespace std;
int main(){
    const int mod=1000000007;
    int n,k;
    cin>>n>>k;
    long long wa[n+1];
    for(long long i=0;i<=n;i++){
        wa[i]=i*(i+1)/2;
    }
    long long x=1;
    for(int i=k;i<=n;i++){
        x+=wa[n]-wa[n-i]-wa[i-1]+1;
        x%=mod;
    }
    cout<<x<<endl;
    return 0;
}

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

using namespace std;

#define ll long long

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

	vector<int> v(n);
	vector<int> wt(n);

	for (int i = 0; i < n; i++)
	{
		cin >> wt[i];
		cin >> v[i];
	}

	vector<vector<ll>> dp(n + 1, vector<ll>(w + 1));
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= w; j++)
		{
			if (i == 0 || j == 0)
			{
				dp[i][j] = 0;
			}
			else if (wt[i - 1] <= j)
			{
				dp[i][j] = max(v[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i -1][j]);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	cout << dp[n][w] << endl;
}

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

using namespace std;
typedef long long ll;
const int MAXN = 60;
const int MAXK = 110;

int n, k;
ll v[MAXN];
ll sumV[MAXN][MAXN];
vector<ll> minusV[MAXN][MAXN];


void solve() {
  for (int i=0;i<=n;i++) {
    for (int j=0;j<=n;j++) {
      if (i + j <= min(k, n)) {
        for (int l=0;l<i;l++) {
          if (v[l] < 0) {
            minusV[i][j].push_back(v[l]);
          } else {
            sumV[i][j] += v[l];
          }
        }
        for (int r=0;r<j;r++) {
          if (v[n-1-r] < 0) {
            minusV[i][j].push_back(v[n-1-r]);
          } else {
            sumV[i][j] += v[n-1-r];
          }
        }
      }
    }
  }
  ll ans = 0;
  for (int i=0;i<=n;i++) {
    for (int j=0;j<=n;j++) {
      if (i + j <= min(k, n)) {
        sort(minusV[i][j].begin(), minusV[i][j].end());
        ll tmp = sumV[i][j];
        for (int x=k-(i+j);x<minusV[i][j].size();x++) {
          tmp += minusV[i][j][x];
        }
        ans = max(ans, tmp);
      }
    }
  }
  cout << ans << endl;
}

int main() {
  cin >> n >> k;
  for (int i=0;i<n;i++) {
    cin >> v[i];
  }
  solve();
}


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

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

typedef long long ll;

int main() {
    ll n, a, b, c, d, e; 
    cin >> n >> a >> b >> c >> d >> e;
    ll min_trans = min(a, min(b, min(c, min(d, e))));
    cout << 4 + n/min_trans + (n%min_trans==0 ? 0 : 1) << endl;
    return 0;
}


Measured memory_bytes: 764
def main():
    N = int(input())
    A=[int(input()) for x in range(N)]

    A.sort()
    s = 0
    e = N - 1
    L = A[0]
    R = A[e]
    ret1 = R - L
    while True:
        ss = s + 1
        ee = e - 1

        b = max(abs(L - A[ss]), abs(R - A[ss])) > max(abs(L - A[ee]), abs(R - A[ee]))

        if b:
            s += 1
            if abs(L - A[s]) < abs(R - A[s]):
                ret1 += abs(R - A[s])
                R = A[s]
            else:
                ret1 += abs(L - A[s])
                L = A[s]
        else:
            e -= 1
            if s == e: break
            if abs(L - A[e]) < abs(R - A[e]):
                ret1 += abs(R - A[e])
                R = A[e]
            else:
                ret1 += abs(L - A[e])
                L = A[e]
        if s == e: break

    # 出力
    print("{}".format(ret1))


if __name__ == '__main__':
    main()


Measured memory_bytes: 7516
import java.util.*;
import java.lang.StringBuilder;

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

        int num = Integer.parseInt(line[0]);
        int length = Integer.parseInt(line[1]);
        
        String[] arr = new String[num];

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

            arr[i] = sc.nextLine();

        }

        Arrays.sort(arr);

        StringBuilder result = new StringBuilder();
        for(int i = 0;i < num;i++){
            result.append(arr[i]);
        }

        System.out.println(result.toString());
    }
}

Measured memory_bytes: 23764
/*  In the name of ALLAH */

#include<bits/stdc++.h>
using namespace std;
/*******  All Required define Pre-Processors and Constants    *******/

#define int long long
#define ull unsigned long long 
#define ld long double
#define mem(a, b) memset(a, (b), sizeof(a))
#define rep(i, j, k) for (int i = j ; i < k ; ++i)
#define rrep(i, j, k) for (int i = j; i > k; --i)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define foreach(i, a) for(auto i: a)
#define forEach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define in(A, B, C) assert( B <= A && A <= C)
#define debug(a) cout << #a << ": " << a << endl
#define Flag(n) cout << "here " << n << endl
#define w(x) int x;cin>>x;while(t--)
#define mp make_pair
#define pb push_back

#define endl '\n';
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int POSITIVE_INFINITY = 9223372036854775807;
const int NEGATIVE_INFINITY = -9223372036854775807;
const int MOD = 1000000007;
const ld PI = acos(-1.0);
 

#define TRACE
#ifdef TRACE
#define see(...) __f(#__VA_ARGS__,__VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr<<name<<" : "<<arg1<<endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma=strchr(names+1,',');cerr.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1, args...);
}
#else
#endif



int32_t main() {
    io;
    // freopen("input.txt","r",stdin); 
    // freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    vector<int>v(n);
    rep(i,0,n)cin>>v[i];
    int ans1=0,ans2=0, sum1=0,sum2=0;
    for(int i= 0 ;i<n;i++){
        sum1+=v[i];
        if(i%2==0 && sum1<=0)ans1+=(1-sum1) , sum1=1;
        if(i%2==1 && sum1>=0)ans1+=(1+sum1) , sum1=-1;
    }
    for(int i = 0 ; i < n;i++){
        sum2+=v[i];
        if(i%2==1 && sum2<=0) ans2+=(1-sum2),sum2=1;
        if(i%2==0 && sum2>=0) ans2+=(sum2+1),sum2=-1;

    }
    cout<<min(ans1,ans2)<<endl;

 

 
    
 
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>

int ceil(int v) {
    if (v % 10 == 0) return v;
    int ans = v - (v % 10);
    return ans + 10;
}

int main() {
    int a[5];
    int min_mod_time = 0, min_mod = 10;
    int ans = 0;
    for (auto &v : a) {
        std::cin >> v;
        if (v % 10 != 0 && v % 10 < min_mod) {
            min_mod = v % 10;
            min_mod_time = v;
        }
    }
    for (auto &v : a) {
        ans += ceil(v);
    }
    ans = ans - ceil(min_mod_time) + min_mod_time;
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll ;
const int MOD = 1e9 + 7;
#define N 2500
ll dp[N];
void init() {
    dp[0] = dp[1] = dp[2] = 1;
    for (int i = 3; i < N; i++) {
        dp[i] = dp[i - 1] + dp[i - 3];
        dp[i] %= MOD;
    }
}

int main() {
    init();
    int n;
    cin >> n;
    if (n < 3) cout << 0 << endl;
    else cout << dp[n-3] << endl;
}


Measured memory_bytes: 3628
// "include" {{{
#include <deque>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <utility>
// }}}
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long 
#define pii pair<int,int> 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

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

vector<int> d(100050);
vector<int> b(100050);
vector<pii > a;

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int q,h,s,d,n;
	cin >> q >> h >> s >> d >> n;
	int sum = 0;
	n *= 1000;
	while(n){
		if(n >= 2000){
			sum += min({n / 2000 * q * 8, n / 2000 * h * 4, n / 2000 * s * 2, n / 2000 * d});
			n %= 2000;
		}
		else if(n >= 1000){
			sum += min({n / 1000 * q * 4,n / 1000 * h * 2,n / 1000 * s});
			n %= 1000;
		}
		else if(n >= 500){
			sum += min({n / 500 * q * 2,n / 500 * h});
			n %= 500;
		}
		else {
			sum += n / 250 * q;
			n %= 250;
		}
	}
	cout << sum << '\n';
	return 0;
}


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

int main(){
    int H, W;
    cin >> H >> W;
    vector<vector<char>> S(H + 2, vector<char>(W + 2, '#'));
    vector<vector<int>> A(H + 2, vector<int>(W + 2, 0));
    vector<vector<int>> B(H + 2, vector<int>(W + 2, 0));
    vector<vector<int>> C(H + 2, vector<int>(W + 2, 0));
    vector<vector<int>> D(H + 2, vector<int>(W + 2, 0));
    
    for(int h = 1; h <= H; h++){
        for(int w = 1; w <= W; w++){
            cin >> S[h][w];
        }
    }
    
    for(int h = 1; h <= H; h++){
        for(int w = 1; w <= W; w++){
            if(S[h][w] == '#')continue;
            int dh = h - 1, dw = w - 1;
            if(0 <= dh){
                A[h][w] = A[dh][w] + 1;
            }
            if(0 <= dw){
                B[h][w] = B[h][dw] + 1;
            }
        }
    }
    
    for(int h = H; h > 0; h--){
        for(int w = W; w > 0; w--){
            if(S[h][w] == '#')continue;
            int dh = h + 1, dw = w + 1;
            if(dh <= H + 1){
                C[h][w] = C[dh][w] + 1;
            }
            if(dw <= W + 1){
                D[h][w] = D[h][dw] + 1;
            }
        }
    }
    
    int ans = 0;
    for(int h = 1; h <= H; h++){
        for(int w = 1; w <= W; w++){
            if(S[h][w] == '#')continue;
            int res = A[h][w] + B[h][w] + C[h][w] + D[h][w] - 3;
            ans = max(ans, res);
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 67072
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

int N, K;
vector<i64> a;

i64 memo[200010][4];

i64 dp(int i, int cnt) {
    if (i >= N) {
        return (cnt <= K) ? 0 : -LINF;
    }
    if (i > N) return -LINF;
    if (cnt > K) return -LINF;

    auto &ret = memo[i][cnt];
    if (~ret) return ret;

    ret = -LINF;
    chmax(ret, dp(i + 2, cnt) + a[i]);
    chmax(ret, dp(i + 3, cnt + 1) + a[i]);
    return ret;
}

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

    read(N);
    a.resize(N);
    read(a);
    K = (N & 1) ? 2 : 1;

    memset(memo, -1, sizeof(memo));

    i64 ans = -LINF;
    chmax(ans, dp(0, 0));
    chmax(ans, dp(1, 1));
    chmax(ans, dp(2, 2));

    print(ans);

    return 0;
}


Measured memory_bytes: 17100
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e4+10;
ll ans;
int n,a,b;
int divide(int x){
	int sum=0;
	while(x){
		sum+=x%10;
		x/=10;
	}
	return sum;
}
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		int q=divide(i);
		if(q>=a&&q<=b)ans+=i;
	}
	cout<<ans<<"\n";
}

Measured memory_bytes: 256
#include <stdio.h>

void swap(int n, int p, int c, int* card){
  int *temp1 = new int[p-1];
  int *temp2 = new int[c];
  for(int i=0; i<p-1; i++){
    temp1[p-1-1-i] = card[n-1-i];
  }
  for(int i=0; i<c; i++){
    temp2[c-1-i] = card[n-p-i];
  }
  for(int i=0; i<c; i++){
    card[n-1-i] = temp2[c-1-i];
  }
  for(int i=0; i<p-1; i++){
    card[n-1-c-i] = temp1[p-1-1-i];
  }
  delete[] temp1;
  delete[] temp2;
}

int main(void){
  int n, r, p, c;
  int i;
  int card[50];

  while(1){
    for(i=0;i<50;i++){
      card[i]=i+1;
    }
    scanf("%d%d", &n, &r);
    if(n==0 && r==0){
      break;
    }
    for(i=0;i<r;i++){
      scanf("%d%d", &p, &c);
      swap(n, p, c, card);
    }
    printf("%d\n", card[n-1]);
  }
}

Measured memory_bytes: 1032
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
#define Add(x, y) x = (x + (y)) % mod
#define Mult(x, y) x = (x * (y)) % mod

signed main(){
    int Q,H,S,D,N; cin>>Q>>H>>S>>D>>N;
    int A = min(2*Q,H);
    int B = min(2*A,S);
    int E = min(2*B,D);
    int ans = 0;
    if(N%2==0) ans = N/2*E;
    else ans = N/2*E+B;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

cnt = 0
step = 0

for i in range(N):
    if A[step] == B[i]:
        cnt += 1
    else:
        step += 1



flag = 0

for j in range(300):
    C = B[cnt+j:]+B[:cnt+j]
    flag = 0
    for i in range(N):
        if A[i] == C[i]:
            flag = 1
            break
    if i == N-1 and flag == 0:
        break
    
    
if flag == 1:
    print('No')
else:
    print('Yes')
    print(' '.join(map(str, C)))

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

using namespace std;

long long arr[500005];

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

    long long n,i;
    long long ans = 0;
    cin>>n;
    for(i=0;i<n-1;i++)cin>>arr[i];
    for(i=0;i<n-2;i++){
        ans+=min(arr[i],arr[i+1]);
    }
    ans+=arr[0];ans+=arr[n-2];
    cout<<ans<<'\n';
    return 0;
}



Measured memory_bytes: 256
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for a in range(n):
  for b in range(k + 1):
    for c in range(2):
      nd = int(s[a])
      for d in range(10):
        na, nb, nc = a + 1, b, c
        if d != 0:
          nb += 1
        if nb > k:
          break
        if nc == 0:
          if d < nd:
            nc = 1
          if d > nd:
            break
        dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    int ans = 0;
    if(a < b) ans = a;
    else ans = b;
    if(c < d) ans += c;
    else ans += d;
    printf("%d\n", ans);
    return 0;
}

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

using namespace std;
const int MAXN = 312345;

int n, d[MAXN];
vector < pair <int, int> > g[MAXN];

void bfs (int s = 0) {
	
	for (int i = 0; i < MAXN; ++i) d[i] = -1;
	d[s] = 0;
	
	queue <int> q;
	q.push(s);

	while (!q.empty()) {

		int u = q.front();
		q.pop();

		// cout <<  u << '\n';


		for (int i = 0; i < (int)g[u].size(); ++i) {
			int v = g[u][i].first;
			int w = g[u][i].second;

			if (d[v] == -1) {
				d[v] = d[u] + w;
				q.push(v);
			}
		}
	}

	for (int i = 0; i < n; ++i) cout << (d[i] % 2) << '\n';



}


int main () {

	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> n;

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

		int u, v, w;
		cin >> u >> v >> w;

		--u; --v;
		w = w % 2;

		g[u].push_back ({v, w});
		g[v].push_back ({u, w});

	}

	bfs ();






	return 0;
}


Measured memory_bytes: 12672
x,n = map(int,input().split())
if n == 0:
  print(x)
else:
  ps= set(map(int,input().split()))
  diff = 0
  while(True):
    if x-diff not in ps:
      print(x -diff)
      break
    elif x + diff not in ps:
      print(x + diff)
      break
    diff +=1


Measured memory_bytes: 61572