akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int MAXN = 4005;

struct disj{
	int pa[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

struct edg{
	int s, e, x;
	bool operator<(const edg &e)const{
		return x < e.x;
	}
};

int n, m;
vector<pi> gph[MAXN];
vector<edg> ed;
int dep[MAXN], par[12][MAXN], pva[12][MAXN];

void dfs(int x, int p){
	for(auto &i : gph[x]){
		if(i.second == p) continue;
		par[0][i.second] = x;
		pva[0][i.second] = i.first;
		dep[i.second] = dep[x] + 1;
		dfs(i.second, x);
	}
}

int get(int s, int e){
	if(dep[e] < dep[s]) swap(s, e);
	int dx = dep[e] - dep[s];
	int ans = 0;
	for(int i=0; i<12; i++){
		if((dx >> i) & 1){
			ans = max(ans, pva[i][e]);
			e = par[i][e];
		}
	}
	for(int i=11; i>=0; i--){
		if(par[i][s] != par[i][e]){
			ans = max({ans, pva[i][s], pva[i][e]});
			s = par[i][s];
			e = par[i][e];
		}
	}
	if(s != e){
		ans = max({ans, pva[0][s], pva[0][e]});
	}
	return ans;
}

int main(){
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int s, e, x;
		scanf("%d %d %d",&s,&e,&x);
		ed.push_back({s, e, x});
	}
	sort(ed.begin(), ed.end());
	lint ans = 0;
	disj.init(n);
	for(auto &i : ed){
		if(disj.uni(i.s, i.e)){
			ans += i.x;
			gph[i.s].push_back(pi(i.x, i.e));
			gph[i.e].push_back(pi(i.x, i.s));
		}
	}
	dfs(1, 0);
	for(int i=1; i<12; i++){
		for(int j=1; j<=n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
			pva[i][j] = max(pva[i-1][j], pva[i-1][par[i-1][j]]);
		}
	}
	int q;
	scanf("%d",&q);
	while(q--){
		int s, e;
		scanf("%d %d",&s,&e);
		printf("%lld\n", ans - get(s, e));
	}
}


Measured memory_bytes: 8560
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

int main() {
  int n; cin >> n;
  vector<int> A(n);
  loop(i,0,n) cin >> A[i];
  int min_ = 0;
  int max_ = 0;
  {
    vector<int> B(n);
    loop(i,0,n) B[i] = A[i];
    sort(B.begin(), B.end());
    min_ = B[0], max_ = B[n-1];
  }
  
  int ans = 100000000;
  loop(k,min_,max_+1) {
    int sum = 0;
    for (auto &&a: A) {
      sum += (a-k)*(a-k);
    }
    ans = min(ans, sum);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3608
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	log.SetFlags(log.Lshortfile)
	n := nextInt()
	s := nextString()
	cnt := 0
	for i := 0; i < n-2; i++ {
		if s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C' {
			cnt++
		}
	}
	fmt.Println(cnt)
}

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

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt32

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type pair struct {
	a, b int
}

type pairs []pair

func (p pairs) Len() int {
	return len(p)
}
func (p pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

const ll MOD = 1e9 + 7;
const ll INF = 1e14;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (int i = (l); i < (r); i++)
#define reper(i, l, r) for (int i = (r)-1; i >= (l); i--)

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

void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll N, K;
    cin >> N >> K;
    vl H(N);
    rep(i, N) cin >> H[i];
    sort(all(H));
    reverse(all(H));
    if(N<=K){
        cout << 0 << endl;
        return 0;
    }
    ll ans = 0;
    repe(i,K,N){
        ans += H[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define x first
#define y second
#define sz(a) ((int)(a.size()))
const int mod = 1812447359;
const int mod2 = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const int MAX = 200005;
const int ZSUV = 10 * 1000 * 1000;
ll a , b , c , d;
map<ll , ll> m;
ll cst(ll x, ll y)
{
	if(x == y)
		return 0;
	if(abs(x - y) > INF)
	{
		if(y * 2 == x)
			return a;
		if(y * 3 == x)
			return b;
		if(y * 5 == x)
			return c;
		assert(false);
	}
	if(y * 2 == x)
		return min(a , d * abs(x - y));
	if(y * 3 == x)
		return min(b , d * abs(x - y));
	if(y * 5 == x)
		return min(c , d * abs(x - y));
	return d * abs(x - y);
}
ll down(ll x , ll y) 
{
	return (x /  y) * y;
}
ll up(ll x , ll y)
{
	return ((x + y - 1) / y) * y;
}
ll A[3] = {2 , 3 , 5};
ll f(ll n)
{
	if(n == 0)
		return 0;
	if(n == 1)
		return d;
	if(m.count(n))
		return m[n];
	ll ans = INF * (ll) INF;
	for(int i = 0; i < 3; i++)
	{
		ans = min(ans , cst(n , up(n , A[i])) + cst(up(n , A[i]) , up(n , A[i]) / A[i]) + f(up(n , A[i]) / A[i]));
		ans = min(ans , cst(n , down(n , A[i])) + cst(down(n , A[i]) , down(n , A[i]) / A[i]) + f(down(n , A[i]) / A[i]));
	}
	return m[n] = ans;
}
int main()
{
	ios_base::sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--)
	{
		m.clear();
		ll n;
		cin >> n;
		cin >> a >> b >> c >> d;
		
		cout << f(n) << endl;
		
	}
}


Measured memory_bytes: 4404
#include<stdio.h>
 
#define M 200000
#define S 2000000000
 
int L[M/2+2],R[M/2+2];
long b1,b2,b3;
 
long mer(int *a,int n,int left,int right,int man){
 
  int i,j,k=0;
  long cou=0;
 
  int na=man-left;
  int nb=right-man;
 
  for(i=0;i<na;i++) L[i]=a[left+i];
  for(i=0;i<nb;i++) R[i]=a[man+i];
 
  L[na]=R[nb]=S;
 
  i=0;
  j=0;
  for(k=left;k<right;k++){
    if(L[i]<=R[j]){
      a[k]=L[i++];
    }else{
       
      a[k]=R[j++];
      cou+=na-i;
    }
  }
  return cou;
}
 
long sort(int *a,int n,int right,int left){
  int man;
  long b1,b2,b3;
   
 
  if(left+1<right){
    man=(left+right)/2;
    b1=sort(a,n,man,left);
    b2=sort(a,n,right,man);
    b3=mer(a,n,left,right,man);
    return b1+b2+b3;
  }else return 0;
}
 
int main(){
  int a[M],n,i;
  long ans=0;
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
 
 
  ans=sort(a,n,n,0);
  printf("%ld\n",ans);
 
  return 0;
}


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

int A, B, C, D;
void solve()
{
	int maxL = max(A, C);
	int minR = min(B, D);
	int ans = minR - maxL;
	if(ans < 0)
		ans = 0;
	cout << ans << endl;
}
int main()
{
	cin >> A >> B >> C >> D;
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main (void){

	int sum = 0;		//????¨???????????´????????????°
	int i = 0 ;			//???????????°
	int j = 0 ;			//??°????????´??°??????????????????????´????????????°

	do{
		char number[1001] = {0};			//1000????????\??????????????????????´??????? 0??§?????????
		scanf("%s", number);				//????????????????????????
		sum = 0 ;							//sum????????????

		for( i = 0 ; i < 1001 ; i++){
			if( '0' <= number[i] && number[i] <= '9'){	//????´???????????????????????????°????????????????????????????????????
				j = number[i] - '0' ;					//int??????j?????°?????¨??????????´?
#ifdef DEBUG
				printf(" %d",j);						//???????¢??????¨
#endif
				sum += j ;
#ifdef DEBUG
				printf(" %d",sum);						//???????¢??????¨
#endif
			}
		}

		/*?¨???????????????????*/
		if(sum){
			printf("%d\n",sum);
		}


	}while(sum);			//0?????????????????????????????¨sum = 0??¨?????????????????????????????¨??????

	return 0;
}

Measured memory_bytes: 2668
#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <unordered_set>
#include <complex>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <cassert>
#include <random>

#define sz(a) (int)((a).size())

using namespace std;

mt19937 rnd(239);

typedef long long ll;
typedef long double ld;

int solve()
{
    ios::sync_with_stdio(0);
    int a;
    if (!(cin >> a))
    {
        return 1;
    }
    int b;
    cin >> b;
    bool ok = 1;
    if (a > b)
    {
        ok = 0;
        swap(a, b);
    }
    const int N = 100;
    int q = a;
    vector<vector<char> > s(N, vector<char>(N, '.'));
    for (int i = 1; a; i += 2)
    {
        for (int j = 0; j <= i && a; j++)
        {
            s[i - j][j] = '#';
            a--;
        }
        if (!a)
        {
            b -= (q - (i + 1) / 2) + 1;
            int x = i + 2, y = 1;
            while (b)
            {
                s[x - 1][y - 1] = s[x - 1][y] = s[x - 1][y + 1] = s[x][y - 1] = s[x][y + 1] = s[x + 1][y - 1] = s[x + 1][y] = s[x + 1][y + 1] = '#';
                y += 2;
                b--;
                if (y > N - 7)
                {
                    x += 2;
                    y = 1;
                }
            }
            break;
        }
    }
    if (ok)
    {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (s[i][j] == '.')
                    s[i][j] = '#';
                else
                    s[i][j] = '.';
    }
    cout << N << ' ' << N << endl;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            cout << s[i][j];
        cout << endl;
    }
    return 0;
}

int32_t main()
{
    #ifdef ONPC
        freopen("in.txt", "r", stdin);
    #endif
    int T = 100;
    //cin >> T;
    for (int i = 1; i <= T; i++)
    {
        #ifdef ONPC
            cerr << "Test #" << i << ":\n";
        #endif
        if (solve())
            break;
        #ifdef ONPC
            cerr << "_______________________________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1000LL / CLOCKS_PER_SEC << " ms" << endl;
    #endif
    return 0;
}


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

struct infor
{
    char s[105];
}x[105];
bool cmp(infor &a,infor &b)
{
    return strcmp(a.s,b.s)<0;
}
int main()
{
    int n,l,i;
    cin>>n>>l;
    for(i=0;i<n;i++)
    {
        cin>>x[i].s;
    }
    sort(x,x+n,cmp);
    for(i=0;i<n;i++)
    {
        cout<<x[i].s;
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <map>
#define ull unsigned long long
#define ll long long
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a,b,c;
    int a_1=0,b_1=0,c_1=0;
    cin >> a >> b >> c;
    char cmp='a';
    while(1){
        if(cmp=='a'){
            cmp=a[a_1];
            if(a_1==a.size()){
                cout << 'A' << endl;
                return 0;
            }
            a_1++;
        }
        else if(cmp=='b'){
            cmp=b[b_1];
            if(b_1==b.size()){
                cout << 'B' << endl;
                return 0;
            }
            b_1++;
        }
        else if(cmp=='c'){
            cmp=c[c_1];

            if(c_1==c.size()){
                cout << 'C' << endl;
                return 0;
            }
            c_1++;
        }
    }


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <fstream>
using namespace std;

//#define FILE_INPUT
//#define DEBUG_MODE

void DebugPrint(vector<long long int> &a, int n)
{
#ifdef DEBUG_MODE
	for (int i = 0; i < min(20, n); ++i) {
		cout << a[i] << ",";
	}
	cout << endl;
#endif
}


int main()
{
#ifdef FILE_INPUT
	ifstream in("test3.txt");
	cin.rdbuf(in.rdbuf());
#endif	/* FILE_INPUT */  

	int n;
	cin >> n;

	vector<long long int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	vector<vector<long long int>> syn(n, vector<long long int>(n, -1));
	vector<vector<long long int>> score(n, vector<long long int>(n, 0));

	for (int i = 0; i < n; ++i) {
		long long int sum = 0;
		for (int j = i; j < n; ++j) {
			sum += a[j];
			syn[i][j] = sum;
		}
		DebugPrint(syn[i], n);
	}
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < n - i; ++j) {
			long long int min_v = -1;
			for (int k = j + 1; k <= j + i; ++k) {
				long long int value = score[j][k - 1] + score[k][j + i];
				if (k == j + 1 || value < min_v) {
					min_v = value;
				}
			}
			score[j][j + i] = syn[j][j + i] + min_v;
			//cout << j << " " << j + i << " " << score[j][j + i] << endl;
		}
	}
	for (int i = 0; i < n; ++i) {
		DebugPrint(score[i], n);
	}

	cout << score[0][n - 1] << endl;

	return 0;
}


Measured memory_bytes: 2816
#include<iostream>
#include<vector>
#define N 500000
#define INF 2000000000
using namespace std;
int c;

void merge(int *A,int l,int m,int r){
  vector<int> L,R;
  for(int i=l;i<m;i++)L.push_back(A[i]);
  for(int i=m;i<r;i++)R.push_back(A[i]);  
  int i=0,j=0;
  L.push_back(INF);
  R.push_back(INF);
   for(int k=l;k<r;k++){
     if(R[j]>L[i])A[k]=L[i++];
     else A[k]=R[j++];
     c++;
  }
}

void mergesort(int *A,int l,int r){
  if(l+1<r){
    int m=(l+r)/2;
    mergesort(A,l,m);
    mergesort(A,m,r);
    merge(A,l,m,r);
  }
}
 
 
int main(){
  int n,S[N];
  cin>>n;
  for(int i=0;i<n;i++)cin>>S[i];
  mergesort(S,0,n);
  for(int i=0;i<n-1;i++)cout<<S[i]<<" ";
  cout<<S[n-1]<<endl<<c<<endl;
  return 0;
}


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

int main(){
    string s,t;
    cin>>s>>t;
    vector<string> ans;
    for(ll i=0;i+t.size()-1<s.size();i++){
        bool f=true;
        rep(j,t.size()){
            if(s[i+j]!='?' && s[i+j]!=t[j]){
                f=false;
            }
        }
        if(f){
            string tmp=s;
            rep(j,t.size()){
                tmp[i+j]=t[j];
            }
            rep(j,s.size()){
                if(tmp[j]=='?'){
                    tmp[j]='a';
                }
            }
            ans.push_back(tmp);
        }
    }
    if(ans.size()==0){
        cout<<"UNRESTORABLE"<<endl;
        return 0;
    }
    sort(ans.begin(),ans.end());
    cout<<ans[0]<<endl;
}


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

int main()
{
    int n;
    cin>>n;
    int a[n+5],b[n+5],c[n+5];
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    for(int i=0;i<n-1;i++)cin>>c[i];

    int sum=0;

    for(int i=0;i<n;i++)
    {
        int k=b[a[i]-1];
        sum+=k;
        if(i!=0)
        {
            int l=a[i-1];
            int r=a[i];
            if(l<r&&abs(l-r)==1)
            {
                sum+=c[l-1];
            }
        }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<int,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
class BIT{
	public:
	//[1,i]
	int n;
	vi bit;
//	int bit[MAZ_N+1];
	BIT(int size){
		n=size;
		bit=vi(n+1);
	}
	Def query(int i){//sum
		ll s=-inf;
		while(i>0){
			s=max(s,bit[i]);
			i-=i&-i;
		}
		return s;
	}
	void add(int i,Def x){
		while(i<=n){
			bit[i]=max(bit[i],x);
			i+=i&-i;
		}
	}
};
vp in;
ll sum=0;
ll n,c;
ll f(){
	BIT bit(n);
	vi dp(n+1);
	rep(i,n)dp[i+1]=dp[i]+in[i].second;
	rep(i,n){
		bit.add(i+1,dp[i+1]-in[i].first);
	}
	ll out=bit.query(n);
	rep(i,n-1)
		out=max(out,-2*(c-in[n-i-1].first)+sum-dp[n-i-1]+bit.query(n-i-1));		
	
	return out;
}
int main(){
	cin>>n>>c;
	in=vp(n);
	rep(i,n){
		cin>>in[i].first>>in[i].second;
		sum+=in[i].second;
	}
	ll out=0;
	out=max(out,f());
	reverse(all(in));
	rep(i,n)in[i].first=c-in[i].first;
	out=max(out,f());
	cout<<out<<endl;
}







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

int main() {
  
  ll n;
  cin >> n;
  
  vector<ll> a(n);
  vector<ll> d(100001);
  ll sum = 0;
  REP(i,n) {
    cin >> a[i]; 
    sum += a[i];
    d[a[i]]++;
  }
  
  ll q;
  cin >> q;
  
  ll b, c;
  REP(i,q) {
    cin >> b >> c;
    sum = sum - b*d[b] + c*d[b];
    d[c] += d[b];
    d[b] = 0;
    
    cout << sum << endl;
  }
}

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

int main(){
	char s[2*100000+1]={};
	char t[2*100000+1]={};
	cin>>s>>t;
	int p=strlen(s);
	int ans=0;
	rep(i,p){
		if(s[i]!=t[i]){
			ans++;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3920
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N;
	cin >> N;
	V<ll> A(N+1);
	rep(i,N+1) cin >> A[i];
	ll ans = 0;
	rep(i,N){
		ll x;
		cin >> x;
		if(x < A[i]){
			ans += x;
			A[i] -= x;
		}else{
			x -= A[i];
			ans += A[i];
			A[i] = 0;
			if(x < A[i+1]){
				ans += x;
				A[i+1] -= x;
			}else{
				ans += A[i+1];
				A[i+1] = 0;
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a) = min((a), (b)))
#define chmax(a, b) ((a) = max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const double pi = acos(-1);
const double eps = 1e-10;

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

const int MAX_V = 1010;

int match[MAX_V];
bool used[MAX_V];
vector<vector<int>> G(MAX_V);

bool dfs(int v){
    used[v] = true;
    for(int i=0; i<G[v].size(); i++){
        int u = G[v][i], w = match[u];

        if(w < 0 || (!used[w] && dfs(w))){
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    
    return false;
}

int bipartite_matching(int V){
    int res = 0;
    memset(match, -1, sizeof(match));
    memset(used, 0, sizeof(used));

    for(int v=0; v<V; v++){
        if(match[v] < 0){
            memset(used, false, sizeof(used));
            if(dfs(v)){
                res++;
            }
        }
    }

    return res;
}

int main(){
    while(1){
        int m, n; cin>>m>>n;
        if(m == 0) return 0;

        vector<int> a(m), b(n);
        for(int i=0; i<m; i++) cin>>a[i];
        for(int i=0; i<n; i++) cin>>b[i];

        int V = m + n;

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(__gcd(a[i], b[j]) != 1){
                    int from = i;
                    int to = m + j;

                    G[from].emplace_back(to);
                    G[to].emplace_back(from);
                }
            }
        }

        cout << bipartite_matching(V) << endl;

        for(int i=0; i<V; i++){
            G[i].clear();
        }
    }
}


Measured memory_bytes: 5076
function Main(input) {
	input = input.split("\n");
	tmp1 = input[1].split(" ");
	tmp2 = input[2].split(" ");
	var n = parseInt(input[0], 10);
	var t = parseInt(tmp1[0], 10);
	var a = parseInt(tmp1[1], 10);

        var q = 9999999999;
        var qi = 0;
	for(var i = 0; i < tmp2.length; i++) {
	   var h = parseInt(tmp2[i], 10);
	   var ht = t - h * 0.006;
	   
       if (abs(ht-a) < abs(q-a)) {
           q = ht;
           qi = i + 1;
       }
	}
	console.log('%d',qi);
}
	function abs(val) {
	  return val < 0 ? -val : val;
	};
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7500
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
struct UnionFind{
    vector<long long> par,height,size;
    UnionFind(ll N): par(N),height(N),size(N){
        for(ll i=0;i<N;i++){
            par.at(i)=i;
            height.at(i)=1;
            size.at(i)=1;
        }
    }

    ll root(ll x){
        if(par.at(x)==x)return x;
        return root(par.at(x));
    }

    void unite(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        if(rx!=ry){
            if(height.at(rx)<height.at(ry)) swap(rx,ry);
            size.at(rx)+=size.at(ry);
            height.at(rx)=max(height.at(ry)+1,height.at(rx));
            par.at(ry)=rx;
        }
    }

    bool same(ll x,ll y){
        if(root(x)==root(y))return true;
        else return false;
    }
    
};
int main(){
    
    ll N,M,K;
    cin>>N>>M>>K;
    vector<ll> A(M),B(M),C(K),D(K);
    for(ll i=0;i<M;i++){
        cin>>A.at(i)>>B.at(i);
    }
    for(ll i=0;i<K;i++){
        cin>>C.at(i)>>D.at(i);
    }
    UnionFind tree(N);
    for(ll i=0;i<M;i++){
        tree.unite(A.at(i)-1,B.at(i)-1);
    }
    vector<ll> tonari(N,0);
    for(ll i=0;i<M;i++){
        tonari.at(A.at(i)-1)++;
        tonari.at(B.at(i)-1)++;
    }

    vector<vector<ll>> block(N);
    for(ll i=0;i<K;i++){
        block.at(C.at(i)-1).push_back(D.at(i)-1);
        block.at(D.at(i)-1).push_back(C.at(i)-1);
    }


    for(ll i=0;i<N;i++){
        ll mfbb=0;
        ll q=tree.root(i);
        for( ll x:block.at(i)){
            if(tree.root(x)==q)mfbb++;
        }
        cout<<tree.size.at(tree.root(i))-tonari.at(i)-1-mfbb<<" ";
    }
}

Measured memory_bytes: 12928
n = int(input())
A = list(map(int, input().split()))
m = 1000
s = 0

for i in range(n):
    if i == n-1:
        if s:
            m += A[i] * s
            s = 0
            break
        else:
            break

    if A[i] < A[i+1] and m > A[i]:
        s = m // A[i]
        m -= A[i] * s
    elif A[i] > A[i+1]:
        if s:
            m += A[i] * s
            s = 0
        else:
            continue

print(m)

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


def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    count = 0
    prev_n = -1
    for n in A:
        count += B[n-1]
        if prev_n == n - 1:
            count+= C[prev_n-1]
        prev_n = n
    print(count)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N - 1)]  # type: "List[int]"
    solve(N, A, B, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define _h cout<<"here"<<endl;
#define fill(a,v) memset(a,v,sizeof(a));
#define all(v) v.begin(),v.end()
#define rep(i,n) for(int i=0;i<n;i+=1)
#define prarr(a,n) rep(i,n) cout<<a[i]<<" \n"[i==n-1];// printf("%s\n"," " );
#define ff first
#define ss second
#define pu push_back
const int inf = 1e9+10;
const ll INF = 1e16+10;
const int MOD = 1e9+7;
const int MAXN = 2e5+10;
 
int main(){
    string s;
    cin>>s;
    if(s=="Cloudy"){cout<<"Rainy"<<endl;}
    if(s=="Sunny"){cout<< "Cloudy"<<endl;}
    if(s=="Rainy"){cout<<"Sunny"<<endl;}
}

Measured memory_bytes: 256
s = input()
t = input()
ns = len(s)
nt = len(t)
ss = []

def match(s,t):
    for i,j in zip(s,t):
        if i == '?':
            continue
        if i != j:
            return False
    return True
    
for i in range(ns-nt+1):
    if match(s[i:i+nt], t):
        s2 = s[:i] + t + s[i+nt:]
        s3 = s2.replace('?','a')
        ss.append(s3)
        
if len(ss) == 0:
    print('UNRESTORABLE')
else:
    print(list(sorted(ss))[0])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)
#include <cstdint>

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

typedef modint<MOD> modi;
// mod. m での a の逆元 a^{-1} を計算する
LL modinv(LL a, LL m) {
    LL b = m, u = 1, v = 0;
    while (b) {
        LL t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int main(){
    LL N;cin >> N;
    LL K;cin >> K;
    vector<modi> A(N);
    rep(i,N)cin >> A[i].a;

    vector<modi> left(N,0);    //自分の左側に自分より小さいものがいくつあるか
    vector<modi> right(N,0);   //右側版


    rep(i,N){
        if(i == 0)left[0] = 0;
        for(int j = 0;j<i;j++){
            if(A[i].a > A[j].a)left[i] += 1;
        }
    }
    rep(i,N){
        if(i == N-1)right[N-1] = 0;
        for(int j = N-1;j>i;j--){
            if(A[i].a>A[j].a)right[i] += 1;
        }
    }
    


    vector<modi> S(N,0),r(N,0),l(N,0);
    
    modi ans = 0;
    modi R = 0,L=0;
    rep(i,N){
        R += right[i];

        L += left[i];

    }



    ans = (R+L)*(K)*(K+1)/2 - L*K;

    cout << ans.a << endl;

}


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

int main(){
	int n;
	cin >> n;
	set<int> a;
	rep(i, n){
		int b;
		cin >> b;
		a.insert(b);
	}

	if(n == a.size())
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

}


Measured memory_bytes: 9600
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int         long long   
#define double      long double
#define endl        "\n"
#define pb          push_back
#define PI          3.1415926535897932384626433832795l
#define F           first
#define S           second
#define mp          make_pair
#define f(i,n)      for(int i=0;i<n;i++)
#define fastio      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v)      (v).begin(),(v).end()
#define rall(v)     (v).rbegin(),(v).rend()
#define gcd(a,b)    __gcd((a),(b))
#define fill(a,value) memset(a,value,sizeof(a));
#define minn(v)     *min_element(v.begin(), v.end());
#define maxx(v)     *max_element(v.begin(), v.end());
#define print(x)    cout<<(x)<<endl;
#define sum(v)+x    accumulate(v.begin(), v.end(),x);
typedef pair<int,int> pii;  
typedef vector<int> vi;
signed main() 
{
    fastio;
    cout << fixed << setprecision(12);
    int n;
    cin>>n;
    vi a(n);
    f(i,n)cin>>a[i];
    int ans=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            ans+=a[i]*a[j];
        }
    }
    print(ans)
    return 0;
}

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

int main(){
    int A,B,C,X;
    int ans = 0;
    cin>>A>>B>>C>>X;
    for(int a=0;a<=A;a++){
        for(int b=0;b<=B;b++){
            for(int c=0;c<=C;c++){
                if(500*a+100*b+50*c==X){
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3576
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
 
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef unsigned int uint;
 
char S[2020][2020];
int P[2020][2020];
int Q[2020][2020];
int R[2020][2020];
int n, m, q;
 
int get(int T[][2020], int x1, int y1, int x2, int y2){
	return T[x2][y2] - T[x1-1][y2] - T[x2][y1-1] + T[x1-1][y1-1];
}
 
void solve(){
	scanf("%d%d%d", &n, &m, &q);
	for(int i=1;i<=n;i++) scanf("%s", S[i]+1);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
		P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + (S[i][j] - '0');
		Q[i][j] = Q[i-1][j] + Q[i][j-1] - Q[i-1][j-1] + (S[i][j] - '0') * (i?(S[i-1][j] - '0'):0);
		R[i][j] = R[i-1][j] + R[i][j-1] - R[i-1][j-1] + (S[i][j] - '0') * (j?(S[i][j-1] - '0'):0);
	}
	rep(u, q){
		int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		int ans = get(P, x1, y1, x2, y2);
		ans -= get(Q, x1+1, y1, x2, y2);
		ans -= get(R, x1, y1+1, x2, y2);
		printf("%d\n", ans);
	}
}
 
int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}


Measured memory_bytes: 53504
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val W = Array(N) { readLine()!! }

    val areNotDuplicated = W.toSet().size == N
    val areMatched = W.reduce { old, new -> if (old.last() == new.first()) { new.last().toString() } else  "-" } != "-"

    println(if (areNotDuplicated && areMatched) "Yes" else "No")
}

Measured memory_bytes: 37996
def main():
    N = int(input())
    *a, = map(int, input().split())
    *b, = map(int, input().split())
    b += [0]

    total_beaten = 0
    carry = 0
    for beat, number in zip(b, a):
        by_prev = min(number, carry)

        total_beaten += by_prev
        number -= by_prev

        by_curr = min(number, beat)
        total_beaten += by_curr

        carry = beat - by_curr

    print(total_beaten)


if __name__ == '__main__':
    main()


Measured memory_bytes: 18624
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
  int key;
  struct Node *right, *left, *parent;
};
typedef struct Node Node;

Node *root, *NIL;

Node * treeMinimum(Node *x) {
  while(x->left != NIL)
    x = x->left;
  return x;
}

Node * find(Node *u, int k) {
  while(u != NIL && k != u->key) {
    if(k < u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

Node * treeSuccessor(Node *x) {
  if(x->right != NIL) return treeMinimum(x->right);
  Node *y = x->parent;
  while(y != NIL && x == y->right) {
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(Node *z) {
  Node *y; // 削除する対象
  Node *x; // yの子

  // 削除する節点を決める
  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);

  // yの子xを決める
  if(y->left != NIL) {
    x = y->left;
  } else {
    x = y->right;
  }

  if(x != NIL) {
    x->parent = y->parent;
  }

  if(y->parent == NIL) {
    root = x;
  } else {
    if(y == y->parent->left) {
      y->parent->left = x;
    } else {
      y->parent->right = x;
    }
  }

  if(y != z) {
    z->key = y->key;
  }
}

void insert(int k) {
  Node *y = NIL;
  Node *x = root;
  Node *z;
  
  z = (Node *)malloc(sizeof(Node));
  z->key   = k;
  z->left  = NIL;
  z->right = NIL;
  
  while(x != NIL) {
    y = x;
    if(z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if(y == NIL) {
    root = z;
  } else {
    if( z->key < y->key) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
}

void inorder(Node *u) {
  if(u == NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node *u) {
  if(u == NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}
  
int main(void) {
  int n, i, x;
  char com[16];
  scanf("%d",&n);
  
  for(i=0;i<n;i++) {
    scanf("%s",com);
    if(!strcmp(com,"find")) {
      scanf("%d",&x);
      Node *t = find(root,x);
      if(t != NIL) printf("yes\n");
      else printf("no\n");
    } else if(!strcmp(com,"insert")) {
      scanf("%d",&x);
      insert(x);
    } else if(!strcmp(com,"print")) {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if(!strcmp(com,"delete")) {
      scanf("%d",&x);
      treeDelete(find(root,x));
    }
  }

  return 0;
}


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

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

using namespace std;

int main()
{
  string l;
  cin >> l;

  ll DIV = 1000000007;
  ll result = 1;
  ll dpzero[100001] = {};
  ll dpone[100001] = {};

  dpzero[0] = 1;
  dpone[0] = 2;
  for (int i = 1; i < l.length(); i++)
  {
    if (l[i] == '1')
    {
      dpzero[i] = dpzero[i - 1] * 3 % DIV;
      dpzero[i] = (dpzero[i] + dpone[i - 1]) % DIV;
      dpone[i] = dpone[i - 1] * 2 % DIV;
    }
    else
    {
      dpzero[i] = dpzero[i - 1] * 3 % DIV;
      dpone[i] = dpone[i - 1] % DIV;
    }
  }

  result = (dpone[l.length() - 1] + dpzero[l.length() - 1]) % DIV;

  cout << result << endl;
}


Measured memory_bytes: 2048
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let L: usize = sc.get();
    let R: usize = sc.get();
    let d: usize = sc.get();
    let mut ans = 0;
    for i in L..=R {
        if i % d == 0 {
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2112
import sys
input = sys.stdin.readline
n = int(input())
a = [(int(input()),1) for i in range(n)]
a += [(int(input()),2) for i in range(n)]
a.sort()
b = list(zip(*a))[1]
mod = 10**9+7
ans = 1
stack = []
for i in range(2*n):
  if not stack or stack[-1] == b[i]:
    stack.append(b[i])
  else:
    ans *= len(stack)
    ans %= mod
    stack.pop()
print(ans)

Measured memory_bytes: 85952
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll INF=(ll)1e18+10;
const double PI=acos(-1);

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 (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

void solve(int cn) {
    int K; cin>>K;
    int comp=7;
    for (int i = 0; i < K+10; ++i) {
        if(comp%K==0){
            cout<<i+1<<endl;
            return;
        }
        comp=(comp*10+7)%K;
    }
    cout<<-1<<endl;
}


#define SINGLE
int main() {
#ifdef SINGLE
    solve(1);
#else
    int N;
    cin>>N;
    for(int i=0;i<N;++i){
        solve(i);
    }
#endif
    return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 2333333
int d,d_,lm,L,dd[2333];
ll po10[23333],ans=0,ww[23333];
void dfs(int x,ll w)
{
	if(x>=lm)
	{
		ll cm=0;
		for(int i=0;i<x;++i) cm+=dd[i]*ww[i];
		if(cm!=d) return;
		ll ca=1;
		for(int i=0;i<x;++i)
		{
			//s[x-1-i]-s[i]=dd[i] is required.
			//0<=x+dd[i]<=9
			int l=i?0:1,r=9;
			l=max(l,-dd[i]);
			r=min(r,9-dd[i]);
			if(l>r) ca=0;
			else ca=ca*(r-l+1);
		}
		if(L%2) ca*=10; //mid can be anything
		ans+=ca;
		return;
	}
	int s=(w%10+10)%10;
	dd[x]=-s; dfs(x+1,(w+dd[x])/10);
	if(s) {dd[x]=10-s; dfs(x+1,(w+dd[x])/10);}
}
void work()
{
	lm=L/2;
	for(int i=0;i<lm;++i)
		ww[i]=po10[L-1-i]-po10[i];
	dfs(0,d);
}
int main()
{
	po10[0]=1;
	for(int i=1;i<23333;++i)
		po10[i]=po10[i-1]*10;
	cin>>d; d_=d; int p=0;
	while(d_) ++p,d_/=10;
	for(L=p;L<=p+p;++L) work();
	cout<<ans<<"\n";
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <string>
#include <stdlib.h>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;

int main(){
    ll a,b;
    cin >> a >> b;
    if (a%2==0 || b%2==0){
        cout << "Even" << endl;
    }else{
        cout << "Odd" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
   // freopen("in.txt","r",stdin);
    long long int n,m;
    queue<long long int>q;
    cin>>n;
    if(n<=9)
        cout<<n<<endl;
    else
    {
        long long int ans;
        long long int cnt = 9;
        for(int i=1; i<=9; i++)
            q.push(i);
        while(!q.empty())
        {
            long long int x = q.front();
            q.pop();
            if(x%10 !=0) {
                    ans = 10*x + x%10-1;
                    q.push(ans);
            cnt++;
            if(cnt == n) {
                cout<<ans<<endl;
                break;
            }

            }
            q.push(10*x + x%10);
            cnt++;
            if(cnt == n) {
                cout<<10*x + x%10<<endl;
                break;
            }
            if(x%10 !=9) {
                    q.push(10*x + x%10+1); cnt++;
            if(cnt == n) {
                cout<<10*x + x%10+1<<endl;
                break;
            }
            }
        }
    }
}


Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int N, W; cin >> N >> W;
	vector<int> v(N), w(N);
	for (int i = 0; i < N;i++) {
		cin >> v[i] >> w[i];
	} 
	vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= W;j++) {
			if (j - w[i] < 0) { dp[i + 1][j] = dp[i][j]; }
			else { dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]); }
		}
	}
	cout << dp[N][W] << endl;
}

Measured memory_bytes: 6716
#include <bits/stdc++.h>
using namespace std;
#define INF 1e18L
#define ll long long 
int main()
{
    ll n,w,i,j;
    cin>>n>>w;
    ll v[n],wt[n]; ll sumv=0;
    for(i=0;i<n;i++)
    {
        cin>>wt[i]>>v[i];
        sumv+=v[i];
    }
    ll dp[sumv+1];
    for(ll i=0;i<=sumv;i++) dp[i]=INF;
    dp[0]=0;
    //dp[i] is the minimum total weight of items with total value exactly i
    for(ll i=0;i<n;i++)
    {
        for(ll j = sumv-v[i];j>=0;j--)
        {
            dp[v[i]+j] = min(dp[v[i]+j],dp[j]+wt[i]);
        }
    }
    ll ans=0;
    for(ll i=0;i<=sumv;i++)
    {
        if(dp[i]<=w)
            ans = max(ans,i);
    }
    cout << ans << "\n";
    
}


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

using namespace std;

int main(){
    int n, a=0, b, count=0, flag=0;

    cin>>n;

    while(n--){
        cin>>a>>b;
        if(a==b){
            count++;
        }
        else{
            count=0;
        }

        if(count>=3){
            flag = 1;
        }
    }

    if(flag){
        cout<<"Yes"<<'\n';
    }
    else{
        cout<<"No"<<'\n';
    }

    return 0;
}

Measured memory_bytes: 3632
O = input()
E = input()
if len(O) > len(E):
    for i in range(len(E)):
        print(O[i],end="")
        print(E[i],end="")
    print(O[-1])
elif len(O) < len(E):
    for i in range(len(O)):
        print(O[i],end="")
        print(E[i],end="")
    print(E[-1])
else:
    for i in range(len(O)):
        print(O[i],end="")
        print(E[i],end="")
    print()

Measured memory_bytes: 3064
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cmath>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<string>
#include<tuple>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define REP(i, n)  for(int i=0; i<(int)(n); i++)
#define REPS(i, n)  for(int i=1; i<=(int)(n); i++)
#define PER(i, n) for(int i=(int)(n)-1; i>= 0; i--)
#define PERS(i, n)  for(int i=(int)(n)-1; i>0; i--)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i!=(c).end(); i++)
#define RFOR(i, c)  for(__typeof((c).rbegin()) i=(c).rbegin(); i!=(c).end(); i++)
#define ALL(container)  (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) (container).size()
#define FILL0(n)  setfill('0') << right << setw(n)
#define mp(a, b)  make_pair(a, b)
#define pb  push_back
#define eb  emplace_back

const int INF = 1<<28;
const int MOD = 1000000007;

int main(){
  ll r, D, x;  cin >> r >> D >> x;
  REPS(i, 10){
    x = r * x - D;
    cout << x << endl;
  }
  return 0;
}

Measured memory_bytes: 256