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

#define rep(i, N) for (int i = 0; i < (N); i++)
#define pb push_back
using ll = long long;

template <typename F>
struct FixPoint : F {
    FixPoint(F&& f) : F(forward<F>(f)) {}
    template <typename... Args>
    decltype(auto) operator()(Args&&... args) {
        return F::operator()(*this, forward<Args>(args)...);
    }
};

template <typename F>
decltype(auto) fp(F&& f) {
    return FixPoint<F>(forward<F>(f));
}

namespace MaxFlow {
    template <typename T>
    struct Edge { int v; T cap, f; };
    
    template <typename T>
    struct DoubledEdge { int v, rev; T cap; };
    
    template <typename T>
    T flow(vector<vector<Edge<T>>> G, int s, int t, T cap_inf) {
        int N = G.size();
        vector<vector<DoubledEdge<T>>> D(N);
        rep(u, N) for (Edge<T> e: G[u]) {
            D[u].pb({e.v, (int)D[e.v].size(), e.cap - e.f});
            D[e.v].pb({u, (int)D[u].size() - 1, e.f});
        }
        T f = 0;
        for (;;) {
            vector<bool> vis(N);
            auto augment = fp(
                [&] (auto&& self, int u, T cap_min) -> T {
                    if (u == t) return cap_min;
                    vis[u] = true;
                    for (DoubledEdge<T>& e: D[u]) if (!vis[e.v] && e.cap > 0) {
                        T df = self(e.v, min(cap_min, e.cap));
                        if (df > 0) {
                            e.cap -= df;
                            D[e.v][e.rev].cap += df;
                            return df;
                        }
                    }
                    return 0;
                }
            );
            T df = augment(s, cap_inf);
            f += df;
            if (df == 0) break;
        }
        return f;
    }
}

namespace MF = MaxFlow;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<MF::Edge<int>>> G(N);
    while (M--) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        G[u].pb({v, c, 0});
    }
    cout << flow(G, 0, N - 1, INT_MAX) << endl;
}



Measured memory_bytes: 3312
#include<iostream>
#include<cstdio>
#define re register
using namespace std;
int t[100000+10];
inline int read()
{
	re int n=0,ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')
		{
			n=(n<<3)+(n<<1)+ch-'0';
			ch=getchar();
		}
	return n;
}
void write(int n)
{
	if(n>=10)write(n/10);
	putchar(n%10+'0');
}
int main()
{
	re int s=0,N,M;
	N=read();
	for(re int i=1;i<=N;++i)
		{
			t[i]=read();
			s+=t[i];
		}
	M=read();
	re int p,x;
	for(re int i=1;i<=M;++i)
		{
			p=read();
			x=read();
			write(s+x-t[p]);
			putchar('\n');
		}
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define LB(c, x) lower_bound(c.begin(), c.end(), x)
#define UB(c, x) upper_bound(c.begin(), c.end(), x)
#define LI(c, x) distance(c.begin(), LB(c, x))
#define UI(c, x) distance(c.begin(), UB(c, x))

// functions
template <class T> T ceil(T a, T b) {
    return (a + b - 1) / b;
}
template <class T> T round(T a, T b) {
    return (a + b / 2) / b;
}
template <class T> T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
template <class T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
template <class T> bool amax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, P;
    cin >> A >> P;
    cout << (A * 3 + P) / 2 << endl;
    return 0;
}


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

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);

    string S;
    cin >> S;

    for(int i=0; i<S.size(); i++)
    {
        if(i % 2)
        {
            if(S[i] == 'R')
            {
                cout << "No\n";
                return 0;
            }
        }
        else
        {
            if(S[i] == 'L')
            {
                cout << "No\n";
                return 0;
            }
        }
    }

    cout << "Yes\n";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1;
int main(){
	int n,m,p[7]={1,2,4,8,16,32};
	cin>>n>>m;
	int ans=0;
	ans=1900*m+100*(n-m);
	ans*=p[m];
	cout<<ans<<endl;

}


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


int main()
{
	int n, num;
	long long x_left, x_right, y_up, y_down;
	cin >> n >> num;

	vector<int> x(n), y(n);
	vector<pair<int, int>> point;
	for (int i = 0;i < n;i++) {
		cin >> x[i] >> y[i];
		point.push_back(make_pair(x[i], y[i]));
	}

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	long long min_s = 10e19;

	for (int i = 0;i < n;i++) {
		for (int j = i;j < n;j++) {
			for (int k = 0;k < n;k++) {
				for (int l = k;l < n;l++) {
					x_left = x[i], x_right = x[j];
					y_down = y[k], y_up = y[l];

					int cnt = 0;
					for (int m = 0;m < n;m++) {
						if (x_left <= point[m].first && point[m].first <= x_right) {
							if (y_down <= point[m].second && point[m].second <= y_up) cnt++;
						}
					}
					if (cnt >= num && (x_right - x_left)*(y_up - y_down) < min_s) {
						min_s = (x_right - x_left)*(y_up - y_down);
					}
				}
			}
		}
	}

	cout << min_s << endl;
    return 0;
}


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

typedef ostringstream OSS; typedef istringstream ISS;
typedef long long LL;
typedef pair<int, int> PII;  typedef pair<LL, LL> PLL;
typedef vector<int>    VI;   typedef vector<VI>   VVI;   typedef vector<VVI>   VVVI;
typedef vector<LL>     VLL;  typedef vector<VLL>  VVLL;  typedef vector<VVLL>  VVVLL;
typedef vector<double> VD;   typedef vector<VD>   VVD;   typedef vector<VVD>   VVVD;
typedef vector<string> VS;   typedef vector<VS>   VVS;   typedef vector<VVS>   VVVS;
typedef vector<bool>   VB;   typedef vector<VB>   VVB;   typedef vector<VVB>   VVVB;
typedef vector<PII>    VPII; typedef vector<VPII> VVPII; typedef vector<VVPII> VVVPII;
typedef vector<PLL>    VPLL; typedef vector<VPLL> VVPLL; typedef vector<VVPLL> VVVPLL;

typedef unsigned int  UI;
typedef vector<UI>    VUI;
typedef vector<VUI>   VVUI;

#define fst first
#define snd second
// #define Y first
// #define X second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
#define ALL(x)  (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define RANGEBOX(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define RANGE(x, l, r) ((l) <= (x) && (x) <= (r))
#define rep(i, N)  for (int i = 0; i < (int)(N); i++)
#define rrep(i, N) for (int i = N - 1; i >= 0; i--)
#define REP(i, init, N)  for (int i = (init); i < (int)(N); i++)
#define RREP(i, N, last) for (int i = (init - 1); i >= last; i--)
#define MAXUD(orig, target) orig = max(orig, target)
#define MINUD(orig, target) orig = min(orig, target)
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

template < typename T > inline T fromString(const string &s) { T res; ISS iss(s); iss >> res; return res; };
template < typename T > inline string toString(const T &a)   { OSS oss; oss << a; return oss.str(); };

template<typename T=int> inline void dump(vector<T> vs, bool ent=false) { rep(i, vs.size()) cout << vs[i] << (i+1==vs.size() ? '\n' : ' '); if (ent) cout << endl; }
template<typename T = int> inline void dump(vector<vector<T>> vs, bool ent = false) { rep(i, vs.size()) dump<T>(vs[i]); if (ent) cout << endl; }

const int    INF  = 0x3f3f3f3f;
const LL     INFL = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = 0x3f3f3f3f;
const int    DX[] = {1,  0, -1, 0};
const int    DY[] = {0, -1,  0, 1};
const double EPS  = 1e-12;
// const double PI   = acos(-1.0);
// lambda: [](T1 x)->T2{return y;}
// simple lambda: [](T x){return x;}

int solve(int n, VI &ds) {
    rep(p, 10) {
        bool ok = true;
        rep(i, n) {
            ok &= ds[i] != p;
        }
        if (ok) return p;
    }
    REP(p, 10, 100) {
        bool ok = true;
        rep(i, n - 1) {
            ok &= ds[i] * 10 + ds[i + 1] != p;
        }
        if (ok) return p;
    }
    REP(p, 100, 1000) {
        bool ok = true;
        rep(i, n - 2) {
            ok &= ds[i] * 100 + ds[i + 1] * 10 + ds[i + 2] != p;
        }
        if (ok) return p;
    }
    return 1000;
}

int main(void) {
    int n;
    cin >> n;
    VI ds(n);
    rep(i, n) cin >> ds[i];

    cout << solve(n, ds) << endl;

    return 0;
}

Measured memory_bytes: 3100
import java.util.*;

public class Main {

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

		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			int p = sc.nextInt();
			if(n==0 && m==0 && p==0) break;
			
			int sum = 0;
			int[] a = new int[n];
			for(int i=0;i<n;i++){
				a[i] = sc.nextInt();
				sum += a[i];
			}
			sum = sum*(100-p);
			
			if(a[m-1]==0) System.out.println("0");
			else System.out.println(sum/a[m-1]);
		}
	}
}

Measured memory_bytes: 27716
from heapq import heappop, heappush
heap = []
N, M = map(int, input().split())
for i in list(map(int,input().split())):
    heappush(heap, i*-1)
for j in range(M):
    num = -((-heappop(heap))//2)
    heappush(heap, num)

print(sum(heap) * - 1)

Measured memory_bytes: 64792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static final int MOD = (int)Math.pow(10, 9);
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		String s = sc.next();
		String t = sc.next();
		int res = 0;
		
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == t.charAt(i)) {
				res++;
			}
		}
		
		System.out.println(res);
	}

    static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;
	
	    public FastReader() {
	      br = new BufferedReader(new InputStreamReader(System.in));
	    }
	  
	    String next() { 
	      while (st == null || !st.hasMoreElements()) {
	        try {
	          st = new StringTokenizer(br.readLine());
	        } catch (IOException  e) {
	          e.printStackTrace();
	        }
	      }
	      return st.nextToken();
	    }
	
	    int nextInt() {
	      return Integer.parseInt(next());
	    }
	
	    long nextLong() {
	      return Long.parseLong(next());
	    }
	
	    double nextDouble() { 
	      return Double.parseDouble(next());
	    }
	
	    String nextLine() {
	      String str = "";
	        try{
	            str = br.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
	      }
	  }
}


Measured memory_bytes: 22484
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll mul(ll a,ll b){
  return (a*b)%mod;
}
ll pow(ll x,ll n){
  if(n==0)return 1;
  ll res=pow(mul(x,x),n/2);
  if(n%2==1)res=mul(res,x);
  return res;
}
ll divi(ll a,ll b){
  return mul(a,pow(b,mod-2));
}
ll add(ll a,ll b){
  return (a+b)%mod;
}

ll N,D,X;
ll dp[2005][2005];

int main(){
  while(1){
    cin>>N>>D>>X;
    if(N==0&&D==0&&X==0)break;
    
    ll ans=0,cnt=D%mod;

    dp[0][0]=1;
    for(int i=1;i<=min(N,D);i++){
      ll sum=0;
      for(int j=1;j<=N;j++){
        sum=add(sum,dp[i-1][j-1]);
        if(j-X>=0)sum=add(sum,mod-dp[i-1][j-X]);
        dp[i][j]=sum;
      }
      ans=add(ans,mul(dp[i][N],cnt));
      //cout<<" "<<cnt<<endl;
      cnt=mul(cnt,(D-i)%mod);
      cnt=divi(cnt,i+1);

    }

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

Measured memory_bytes: 32492
<?php

fscanf(STDIN, '%d %d', $n, $max_time);

$min_cost = 10000;
for ($i=0; $i < $n; $i++) {
    fscanf(STDIN, '%d %d', $c, $t);
    if ($t <= $max_time && $c < $min_cost) {
        $min_cost = $c;
    }
}

echo $min_cost === 10000
    ? 'TLE'
    : $min_cost;

Measured memory_bytes: 4856
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
#import queue
from copy import copy, deepcopy
from operator import itemgetter

import bisect#2分探索
#bisect_left(l,x), bisect(l,x)
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#q=heapq.heapify(l),heappush(q,a),heappop(q)

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = int(input())
N, A, B = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入


div, mod=N//(A+B), N%(A+B)

count=div*A
count+=min(mod,A)

print(count)

Measured memory_bytes: 38384
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int odp = n;
    vector<int> lewo(n);
    if (s[0] == 'W')
        lewo[0] = 1;
    for (int i = 1; i < n; ++i)
    {
        lewo[i] = lewo[i - 1];
        if (s[i] == 'W')
            ++lewo[i];
    }
    vector<int> prawo(n);
    if (s[n - 1] == 'E')
        prawo[n - 1] = 1;
    for (int i = n - 2; i >= 0; --i)
    {
        prawo[i] = prawo[i + 1];
        if (s[i] == 'E')
            ++prawo[i];
    }
    for (int i = 0; i < n; ++i)
    {
        int il = 0;
        if (i != 0)
            il += lewo[i - 1];
        if (i != n - 1)
            il += prawo[i + 1];
        odp = min(odp, il);
    }
    cout << odp;
    return 0;
}


Measured memory_bytes: 2964
N, W = map(int, input().split())

DP = [-1] * (W+1)
DP[W] = 0

def maxv(i, v):
    if i >= 0:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    for i in range(1, W+1):
        if DP[i] >= 0:
            maxv(i-w, DP[i]+v)
            maxv(0, DP[i-w])

print(DP[0])


Measured memory_bytes: 42476
#include <bits/stdc++.h>
using namespace std;
int long long a3;
int long long x;
int long long a1=2,a2=1;
int long long fibo(int long long n){
    while(n>=2){
        a3=a2+a1;
        a1=a2;
        a2=a3;
        n--;
    }
    return a3;
}
    
    
    int main(){
        cin>>x;
        if(x==0)  cout<<"2"<<endl;
        else if(x==1)  cout<<"1"<<endl;
        else cout<<fibo(x)<<endl;
    }


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1<<14|3,mo=998244353;
const ll MOD=7LL*mo*mo;
void add(int &x,int y){x=(x+y)%mo;}
int n,m,f[202][N],g[N],fac[N],ifac[N];
inline int power(int a, int n) {
	int res=1;
	while (n) {
		if (n&1) res=1LL*res*a%mo;
		a=1LL*a*a%mo; n>>=1;
	}
	return res;
}
void init(int n){
	fac[0]=1;rep(i,1,n)fac[i]=1LL*fac[i-1]*i%mo;
	ifac[n]=power(fac[n],mo-2);per(i,n-1,0)ifac[i]=1LL*ifac[i+1]*(i+1)%mo;
}
inline void exgcd(int a, int b, int &x, int &y) {
	if (!b) {x=1; y=0; return;}
	exgcd(b,a%b,y,x); y-=a/b*x;
}
inline int inv(int a) {int x,y; exgcd(a,mo,x,y); return x>=0 ? x : x+mo;}
inline void fft(int *a, int n, int tp) {
	static int w[N];
	for (int i=1,j=0; i<n; i++) {
		for (int k=n>>1; !((j^=k)&k); k>>=1);
		if (i<j) swap(a[i],a[j]);
	}
	for (int j=2; j<=n; j<<=1) {
		w[0]=1; w[1]=power(3,(mo-1)/j); w[1]=tp==1?w[1]:inv(w[1]); int m=(j>>1)-1; //mo-1
		rep(i,2,m) w[i]=1LL*w[i-1]*w[1]%mo;
		for (register int i=0; i<n; i+=j) rep(k,0,m) {
			int x=1LL*a[i+k+(j>>1)]*w[k]%mo;
			a[i+k+(j>>1)]=a[i+k]-x>=0?a[i+k]-x:a[i+k]-x+mo;
			a[i+k]=a[i+k]+x<mo?a[i+k]+x:a[i+k]+x-mo;
		}
	}
}
inline void mul(int *_a, int *_b, int n1, int n2, int *c){
	static int a[N],b[N];int n;for(n=1;n<=n1+n2-2;n<<=1);
	if(n<=128){
		static ll _c[N];rep(i,0,n1-1+n2-1)_c[i]=0;
		rep(i,0,n1-1)rep(j,0,n2-1){
			_c[i+j]+=1LL*_a[i]*_b[j];
			_c[i+j]=_c[i+j]<MOD?_c[i+j]:_c[i+j]-MOD;
		}
		rep(i,0,n1-1+n2-1)c[i]=_c[i]%mo;
		return;
	}
	rep(i,0,n1-1)a[i]=_a[i];rep(i,n1,n-1)a[i]=0;//WA!
	rep(i,0,n2-1)b[i]=_b[i];rep(i,n2,n-1)b[i]=0;
	fft(a,n,1);fft(b,n,1);rep(i,0,n-1)a[i]=1LL*a[i]*b[i]%mo;
	int ni=inv(n);fft(a,n,-1);rep(i,0,n-1)c[i]=1LL*a[i]*ni%mo;
}
int main() {
	read(n);read(m);f[0][0]=1;init(N-1);
	rep(j,1,m){
		memcpy(g,f[j-1],sizeof(f[j-1]));
	//	rep(i,0,n)printf("%d %d:%d\n",j,i,g[i]);
		static int a[N],b[N],c[N];
		rep(i,0,n)a[i]=1LL*g[i]*ifac[i]%mo;
		rep(i,0,n)b[i]=ifac[i+2];
		mul(a,b,n+1,n+1,c);
	//	rep(i,0,n)c[i]=0;
	//	rep(i,0,n)rep(j,0,n-i)add(c[i+j],1LL*a[i]*b[j]%mo);
		rep(i,0,n)c[i]=1LL*c[i]*fac[i+2]%mo;
		rep(i,0,n)f[j][i]=((c[i]+1LL*g[i]*(1LL*i*(i+1)/2+1-(i+2)*(i+1)/2))%mo+mo)%mo;
	}
	rep(i,0,n)f[m][i]=(f[m][i]%mo+mo)%mo;
	int res=0;rep(i,0,n)add(res,1LL*f[m][i]*fac[n]%mo*ifac[i]%mo*ifac[n-i]%mo);
	cout<<res;
	return 0;
}


Measured memory_bytes: 12288
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

#define LL long long 

const int maxn=3e5+1e2;
const int maxs=maxn*4;

struct seg
{
	int num;
	LL sum;
}t1[maxs],t2[maxs];

int a[maxn],num[maxn],siz[maxn];

map <int,int> mp;

void maintain(int l,int r,int now)
{
	t1[now].num=t1[now<<1].num+t1[now<<1|1].num;
	t1[now].sum=t1[now<<1].sum+t1[now<<1|1].sum;
	t2[now].num=t2[now<<1].num+t2[now<<1|1].num;
	t2[now].sum=t2[now<<1].sum+t2[now<<1|1].sum;
}

void build(int l,int r,int now)
{
	if(l==r)
	{
		t2[now].num+=siz[l];
		t2[now].sum+=(LL)siz[l]*num[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,now<<1);
	build(mid+1,r,now<<1|1);
	maintain(l,r,now);
}

int p,v;
void update(int l,int r,int now)
{
	if(l==r)
	{
		t1[now].num++;
		t2[now].num--;
		t1[now].sum+=v;
		t2[now].sum-=v;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid)update(l,mid,now<<1);
	else update(mid+1,r,now<<1|1);
	maintain(l,r,now);
}

LL query1(int l,int r,int now,int k)
{
	if(t1[now].num==k)return t1[now].sum;
	if(l==r)return t1[now].sum/t1[now].num*k;
	int mid=(l+r)>>1;
	if(t1[now<<1|1].num>=k)return query1(mid+1,r,now<<1|1,k);
	return query1(l,mid,now<<1,k-t1[now<<1|1].num)+t1[now<<1|1].sum;
}

LL query2(int l,int r,int now,int k)
{
	if(t2[now].num==k)return t2[now].sum;
	if(l==r)return t2[now].sum/t2[now].num*k;
	int mid=(l+r)>>1;
	if(t2[now<<1].num>=k)return query2(l,mid,now<<1,k);
	return query2(mid+1,r,now<<1|1,k-t2[now<<1].num)+t2[now<<1].sum;
}

int main()
{
	int n;
	scanf("%d",&n);
	int nn=n;
	n*=3;
	for(int i=1;i<=n;i++){scanf("%d",&a[i]);num[i]=a[i];}
	sort(num+1,num+n+1);
	int m=unique(num+1,num+n+1)-num-1;
	for(int i=1;i<=m;i++)mp[num[i]]=i;
	for(int i=1;i<=n;i++)siz[mp[a[i]]]++;
	build(1,m,1);
	LL ans=-1e17;
	for(int i=1;i<=n;i++)
	{
		p=mp[a[i]],v=a[i];
		update(1,m,1);
		if(i<nn||i>2*nn)continue;
		ans=max(ans,query1(1,m,1,nn)-query2(1,m,1,nn));
	}
	printf("%lld\n",ans);
	return 0;
}

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

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

using namespace std;
using namespace __gnu_pbds;

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

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

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

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const double EPS = 1e-9;
const ll MOD =998244353;
const ll hell=1000000007;
const int INF = 1e18;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

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

double startTime;
double getCurrentTime() {
    return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };

const int N=100005;
int dp[101][N];


void solve()
{
    
    
    int n,k;
    cin>>n>>k;
    int a[n+1];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dp[0][0]=1;int pre[k+1];
    
    for(int i=1;i<=n;i++)
    {
        pre[0]=dp[i-1][0];
        for(int j=1;j<=k;j++)
            pre[j]=(pre[j-1]+dp[i-1][j])%hell;
        for(int j=0;j<=k;j++)
        {
            
            int l=j-min(j,a[i]);
            dp[i][j]=(pre[j]-(l>=1?pre[l-1]:0)+hell)%hell;
        }
    
    }
    cout<<dp[n][k]<<endl;
    
    
    
    
    
}


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






Measured memory_bytes: 79232
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1e9;
const int MOD = 1e9+7;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...)
#define print(...)
#endif

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

	int n, k; cin >> n >> k;
	string s; cin >> s;
	vector<pair<int, char>> a;
	char cur = 'x';
	int cnt = 0;
	rep(i, n) {
		if (cur=='x') {
			cur = s[i];
			cnt++;
		} else if (cur==s[i]) {
			cnt++;
		} else if (cur!=s[i]) {
			a.emplace_back(cnt, cur);
			cur = s[i];
			cnt = 1;
		}
	}
	a.emplace_back(cnt, cur);
	int m = sz(a);
	vector<pair<int, char>> ss(m+1, {0, 'x'});
	rep(i, m) ss[i+1] = {ss[i].fi+a[i].fi, a[i].se};
	// rep(i, m+1) cout << ss[i].fi << "/" << ss[i].se << " ";
	// cout << endl;
	int ans = 0;
	rep(i, m) {
		if (i>0 && ss[i+1].se=='0') continue;
		int r = i+2*k+1;
		if (i==0 && ss[i+1].se=='0') r--;
		r = min(r, m);
		int l = i;
		debug(i, l ,r, ss[r].fi-ss[l].fi);
		chmax(ans, ss[r].fi-ss[l].fi);
	}
	cout << ans << endl;
}

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

int main(void)
{
  char s_d[128];  char t[128];
  scanf("%s %s",s_d,t);
  int len=(int)strlen(s_d);
  int len2=(int)strlen(t);
  int flag=0;

  for(int i=len-len2;i>=0;i--){
    int k=0;
    int count=0;
    for(int j=i;j<i+len2;j++){
      if(s_d[j]==t[k++]||s_d[j]=='?'){
        count++;
      }
    }
    if(flag!=1){
      if(count==len2){
        flag=1;
        int l=0;
        for(int j=i;j<i+len2;j++){
          s_d[j]=t[l++];
        }
      }
    }
  }


  if(flag==0){
    puts("UNRESTORABLE");
    return 0;
  }


  for(int i=0;i<len;i++){
    if(s_d[i]=='?'){
      s_d[i]='a';
    }
  }
  printf("%s\n",s_d);
  return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String t = sc.nextLine();
        System.out.println(calc(s, t));
    }

    public static int calc(String s, String t){
        int answer = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != t.charAt(i)){
                answer++;
            }
        }
        return answer;
    }
}


Measured memory_bytes: 42720
uses math;
var
  a:array[0..10000]of longint;
  n,x,i,sum:longint;
 procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
begin
  readln(n,x);
  for i:=1 to n do
    begin
	  read(a[i]);
	end;
  sort(1,n);
  i:=1;
  while (x>=a[i])and(i<=n) do
    begin
	  x:=x-a[i];
	  inc(i);
	end;
  if (x<>0) and (i=n+1) then dec(i);
  writeln(max(0,i-1));
end.

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();
		int[] A = new int[N];
		long[] B = new long[N+1];
		int[] C = new int[N];
		long ans = 0;
		for (int i = 0; i < N; i++) {
			A[i] = scan.nextInt();
			B[A[i]]++;
		}

		for (int i = 1; i < N+1; i++) {
			ans += B[i]*(B[i]-1)/2;
		}

		for (int i = 0; i < N; i++) {
			System.out.println(ans - B[A[i]] + 1);
		}

	}

}

Measured memory_bytes: 75540
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
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; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll l, r; cin >> l >> r;

    if (r - l + 1 >= 2019) {
        cout << 0 << endl;
        return 0;
    } else {
        ll ans = INF;
        RANGE(i, l, r) RANGE(j, i+1, r) {
            chmin(ans, i*j % 2019);
        }
        cout << ans << endl;
    }
    
}

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

ll N, A[101010];

ll up(ll idx){
    if(idx + 1 == N)return idx;
    if(A[idx] <= A[idx + 1])return up(idx + 1);
    return idx;
}
ll down(ll idx){
    if(idx + 1 == N)return idx;
    if(A[idx] >= A[idx + 1])return down(idx + 1);
    return idx;
}

int main(){
    
    cin >> N;
    for(ll i = 0; i < N; i++)cin >> A[i];
    ll ans = 0;
    for(ll idx = 0; idx < N; idx++){
        idx = max(up(idx), down(idx));
        ans++;
    }
    cout << ans << endl;

    return 0;
}


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

int main() {
  std::multiset<int> a;
  int tmp;
  for (int i = 0; i < 6; i++) {
    std::cin >> tmp;
    a.insert(tmp);
  }

  for (int i = 1; i <= 4; i++) {
    if (3 <= a.count(i)) {
      std::cout << "NO" << std::endl;
      return 0;
    }
  }

  std::cout << "YES" << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
using namespace std;
typedef long long unsigned int ll;

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

int main(void){

    int W, H, N;
    cin >> W >> H >> N;
    int x[N], y[N], a[N];
    for(int i = 0; i < N; i++){
        cin >> x[i] >> y[i] >> a[i];
    }

    pair<int, int> px = make_pair(0,W);
    pair<int, int> py = make_pair(0,H);

    for(int i = 0; i < N; i++){
        switch(a[i]){
            case 1:
                px.first = max(px.first, x[i]);
                break;
            case 2:
                px.second = min(px.second, x[i]);
                break;
            case 3:
                py.first = max(py.first, y[i]);
                break;
            case 4:
                py.second = min(py.second, y[i]);
                break;
            default:
                break;
        }
    }

    if((px.second - px.first) < 0 || (py.second - py.first) < 0){
        cout << "0" << endl;
    }else{
        cout << abs(px.second - px.first) * abs(py.second - py.first) << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cctype>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int ans, p, q, a, n;

void dfs(int i, int x, int y, int lim){
    if (i == n) return;
    FOR(k,1,lim){
        int xx = x*k + y, yy = y * k;
        if (yy > a) break;
        if (p * yy == q * xx) ans++;
        else if (p * yy > q * xx) dfs(i+1, xx, yy, k);
    }
}

int main() {
    while (cin >> p >> q >> a >> n, n){
        int d = __gcd(p, q);
        p /= d;
        q /= d;
        ans = 0;
        dfs(0, 0, 1, a);
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  map<int, int> count;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
    count[A[i]]++;
  }
  long long total = 0;
  for(const auto& m : count) {
    int value = m.second;
    if(value < 2) continue;
    total += 1LL * value * (value - 1) / 2;
  }
  
  for(int i = 0; i < N; i++) {
    cout << total - count[A[i]] + 1 << endl;
  }
}

Measured memory_bytes: 8960
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;

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

void solve() {
    int n;
    cin >> n;
    if (n == 22) cout << "Christmas Eve Eve Eve" << endl;
    if (n == 23) cout << "Christmas Eve Eve" << endl;
    if (n == 24) cout << "Christmas Eve" << endl;
    if (n == 25) cout << "Christmas" << endl;
}

int main() {
    solve();
    
    return 0;
}

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

int main() {
	int x,y;
	while (1) {
		cin >>x>>y;
		if (x==0 && y==0) break;
		if (x<=y) {
			cout <<x<<" "<<y<<endl;
		} else {
			cout <<y<<" "<<x<<endl;
		}
	}
}



Measured memory_bytes: 2996
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#define ll long long

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<double> p(n,0.0);
  for( int i = 0 ; i < n ; i++ ){
    double cu;
    cin >> cu;
    p[i] = cu;
  }
  vector< vector<double> > dp( n+1 , vector<double>(n+1,0.0));
  dp[0][1] = p[0];//prob of head
  dp[0][0] = 1-p[0];

  for( int i = 1 ; i < n ; i++ ){
    for( int j = 0 ; j <=  i+1 ; j++ ){
      dp[i][j] += dp[i-1][j] * (1-p[i]); 
    }
    for( int j = 0 ; j <=  i+1 ; j++ ){
      dp[i][j+1] += dp[i-1][j] * (p[i]); 
    }
  }
//  for( int i = 0 ; i < n ; i++ ){
//    for( int j = 0 ; j <= i + 1; j++ ){
//      cout << dp[i][j] << " " ;
//    }
//    cout << endl;
//  }
  double ret = 0.0;
  for( int i = (n+1)/2 ; i <= n ; i++ ){
    ret += dp[n-1][i];
  }
  printf("%.10lf\n",ret);
  return 0;
}


Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << "[(" << __LINE__ << ") " << (#x) << "]: " << x << endl;

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

    int d;
    cin >> d;
    
    int c[26];
    for (int& e: c) cin >> e;

    int s[d][26];
    for (int i=0; i<d; i++) {
        for (int j=0; j<26; j++) {
            cin >> s[i][j];
        }
    }

    int t[d];
    for (int& e : t) cin >> e;

    int last[26] = {};

    ll cur = 0;
    for (int i=0; i<d; i++) {
        cur += s[i][t[i]-1];
        last[t[i]-1] = i+1;

        for (int j=0; j<26; j++) {
            cur -= c[j] * (i-last[j]+1);
        }
        cout << cur << "\n";
    }
}


Measured memory_bytes: 3648
#include<stdio.h>
int main(void)
{
	char c;
	scanf("%c",&c);

	if(c=='a'){
		printf("vowel\n");
	}
	
	else if(c=='i'){
		printf("vowel\n");
	}
	
	else if(c=='e'){
		printf("vowel\n");
	}
	
	else if(c=='o'){
		printf("vowel\n");
	}
	
	else if(c=='u'){
		printf("vowel\n");
	}
	
	else{
		printf("consonant\n");
	}
	return 0;
}


Measured memory_bytes: 128
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; ( iter = $ iter : ident , $ ( $ r : tt ) * ) => { let s = { use std :: io :: Read ; let mut s = String :: new ( ) ; std :: io :: stdin ( ) . read_to_string ( & mut s ) . unwrap ( ) ; s } ; let mut $ iter = s . split_whitespace ( ) ; input_inner ! { $ iter , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let s = { use std :: io :: Read ; let mut s = String :: new ( ) ; std :: io :: stdin ( ) . read_to_string ( & mut s ) . unwrap ( ) ; s } ; let mut iter = s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; }
macro_rules ! input_inner { ( $ iter : expr ) => { } ; ( $ iter : expr , ) => { } ; ( $ iter : expr , mut $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let mut $ var = read_value ! ( $ iter , $ t ) ; input_inner ! { $ iter $ ( $ r ) * } } ; ( $ iter : expr , mut $ var : ident $ ( $ r : tt ) * ) => { input_inner ! { $ iter , mut $ var : usize $ ( $ r ) * } } ; ( $ iter : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ iter , $ t ) ; input_inner ! { $ iter $ ( $ r ) * } } ; ( $ iter : expr , $ var : ident $ ( $ r : tt ) * ) => { input_inner ! { $ iter , $ var : usize $ ( $ r ) * } } ; }
macro_rules ! read_value { ( $ iter : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ iter , $ t ) ) ,* ) } ; ( $ iter : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ iter , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ iter : expr , { chars : $ base : expr } ) => { read_value ! ( $ iter , String ) . chars ( ) . map ( | c | ( c as u8 - $ base as u8 ) as usize ) . collect ::< Vec < usize >> ( ) } ; ( $ iter : expr , { char : $ base : expr } ) => { read_value ! ( $ iter , { chars : $ base } ) [ 0 ] } ; ( $ iter : expr , chars ) => { read_value ! ( $ iter , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ iter : expr , char ) => { read_value ! ( $ iter , chars ) [ 0 ] } ; ( $ iter : expr , usize1 ) => { read_value ! ( $ iter , usize ) - 1 } ; ( $ iter : expr , $ t : ty ) => { $ iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) } ; }
fn main() {
    input! { s: {chars: '0'} };
    let n = s.len();
    if s[n - 1] == 1 || s[0] == 0 {
        println!("{}", -1);
        return;
    }
    let mut par = vec![0; n - 1];
    let mut root = 0;
    for i in (0..n / 2).rev() {
        if s[i] != s[n - 2 - i] {
            println!("{}", -1);
            return;
        }
        par[i] = root;
        if s[i] == 1 {
            root = i + 1;
        }
    }
    for i in 0..n - 1 {
        println!("{} {}", par[i] + 1, i + 2);
    }
}


Measured memory_bytes: 7292
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.C_Challenge
{
    class ABC_050
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] input = Console.ReadLine().Split(' ');
            var array = new int[n];
            var cnts = new int[n];
            for (int i = 0; i < n; i++)
            {
                cnts[int.Parse(input[i])]++;
            }
            bool even = n % 2 == 0;
            int itr = even ? 1 : 2;
            if (!even && cnts[0] != 1)
            {
                Console.WriteLine(0);
                return;
            }

            int pairCnt = 0;
            for (; itr < n; itr += 2)
            {
                if (cnts[itr] != 2)
                {
                    Console.WriteLine(0);
                    return;
                }
                else
                {
                    pairCnt++;
                }
            }

            long allPat = 1;
            for(int i = 0; i < pairCnt; i++)
            {
                allPat *= 2;
                allPat %= 1000000007;
            }

            Console.WriteLine(allPat);
        }
    }
}


Measured memory_bytes: 21216
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, a[N][N];
int p, x, cur_x, cur_y, d;

void Move(){
    cur_y += d;
    if(cur_y == m){
        cur_x++;
        cur_y=m-1;
        d = -1;
    } else if(cur_y == -1){
        cur_x++;
        cur_y=0;
        d = 1;
    }
}

int main(){
    while(~scanf("%d %d", &n, &m)){
        cur_x = cur_y = 0;
        d = 1;
        scanf("%d", &p);
        for(int i=1; i<=p; i++){
            scanf("%d", &x);
            for(int j=0; j<x; j++){
                a[cur_x][cur_y] = i;
                Move();
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                printf("%d%c", a[i][j], j==m-1?'\n':' ');
            }
        }
    }
    return 0;
}


Measured memory_bytes: 384
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()

    ret = 0
    for n in range(N):
        if A[n] % 2 != 0 and (n+1) % 2 != 0:
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10220
#include<bits/stdc++.h>
using namespace std;
int a[100000];
int n;
long long ans[100000],all,t;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		all+=a[i];
		if(i%2==0)
		t+=a[i];
	}
	all/=2;
	t-=all;
	ans[0]=t;
	for(int i=1;i<n;i++)
	{
		ans[i]=a[i-1]-ans[i-1];
	}
	for(int i=0;i<n;i++)
	{
		ans[i]*=2;
	}
	for(int i=0;i<n;i++)
	cout<<ans[i]<<" ";
	return 0;
}

Measured memory_bytes: 2432
n, w = gets.split.map &:to_i

wv = []

n.times{
	w_temp, v_temp = gets.split.map &:to_i
	wv << [w_temp, v_temp]
}

cost = Array.new(w + 1, 0)

(1..n).each.with_index(0){ |nn, i| 
	w.downto(wv[i][0]).each{ |ww|
		temp = cost[ww - wv[i][0]] + wv[i][1]
		if cost[ww] < temp then
			cost[ww] = temp
		end
	}
}

puts cost[w]


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

#define pb push_back
#define ll long long
#define mp make_pair
#define F first
#define S second
using namespace std;
void data() {
	#ifdef NURS
		freopen("main.in", "r", stdin);
		freopen("main.out", "w", stdout);
	#endif
}
const int N = 1e5 + 100;
const int mod = 1e9 + 7;
ll dp[N];
int main()
{
	data();
	int n, w;
	cin >> n >> w;
	int a[n + 1], b[n + 1];
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i] >> b[i];
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = w - a[i]; j >= 0; j--)
		{
			dp[j + a[i]] = max(dp[j + a[i]], dp[j] + b[i]);
		}
	}
	ll mx = 0;
	for (int i = 1; i <= w; i++)
	{
		mx = max(mx, dp[i]);
	}
	cout << mx;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;
int main() {
    int n; cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h.at(i);
    int max = 0;
    rep(i, n-1){
        if(max < h.at(i)) max = h.at(i);
        if(max > h.at(i+1) + 1){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3740
#include<cctype>
#include<cstdio>
#include<vector>
#include<cstring>

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

using namespace std;

typedef vector<int> polynomial;

const polynomial ZERO(51,0);

void operator+=(polynomial &p,const polynomial &q){ rep(i,51) p[i]+=q[i]; }
void operator-=(polynomial &p,const polynomial &q){ rep(i,51) p[i]-=q[i]; }

polynomial operator-(const polynomial &p,const polynomial &q){
	polynomial r=p;
	rep(i,51) r[i]-=q[i];
	return r;
}

polynomial parse(const char *s){
	polynomial p(51);
	int len=strlen(s),a=0;
	rep(i,len+1){
		if(i==len || s[i]=='x'){
			if(a==0) a=1; // 係数 1 が省略されていた
			int e=0;
			if(s[i]=='x'){
				i++;
				if(s[i]!='^'){
					e=1;
				}
				else{
					i++;
					for(;isdigit(s[i]);i++) e=e*10+(s[i]-'0');
				}
			}
			p[50-e]=a;
			a=0;
		}
		else{
			a=10*a+(s[i]-'0');
		}
	}
	return p;
}

void print(const polynomial &p){
	bool b=false;
	rep(i,51) if(p[i]>0) {
		int e=50-i;
		if(b) putchar('+');
		if(p[i]>1 || e==0) printf("%d",p[i]);
		if(e>=1) putchar('x');
		if(e>=2) printf("^%d",e);
		b=true;
	}
	puts(b?"":"0");
}

const int V_MAX=50;
const int E_MAX=500;

template<class T>
struct graph{
	int n,m,head[V_MAX],next[2*E_MAX],to[2*E_MAX];
	T capa[2*E_MAX],flow[2*E_MAX];

	void init(int N){
		n=N;
		m=0;
		rep(u,n) head[u]=-1;
	}

	void add_undirected_edge(int u,int v,T ca){
		next[m]=head[u]; head[u]=m; to[m]=v; capa[m]=ca; flow[m]=ZERO; m++;
		next[m]=head[v]; head[v]=m; to[m]=u; capa[m]=ca; flow[m]=ZERO; m++;
	}
};

const polynomial INF(51,1<<29);

int layer[V_MAX],now[V_MAX];

template<class T>
bool make_layer(const graph<T> &G,int s,int t){
	int n=G.n;
	rep(u,n) layer[u]=(u==s?0:-1);

	int head=0,tail=0;
	static int Q[V_MAX]; Q[tail++]=s;
	while(head<tail && layer[t]==-1){
		int u=Q[head++];

		for(int e=G.head[u];e!=-1;e=G.next[e]){
			int v=G.to[e];
			T capa=G.capa[e],flow=G.flow[e];

			if(capa-flow>ZERO && layer[v]==-1){
				layer[v]=layer[u]+1;
				Q[tail++]=v;
			}
		}
	}

	return layer[t]!=-1;
}

template<class T>
T augment(graph<T> &G,int u,int t,T water){
	if(u==t) return water;

	for(int &e=now[u];e!=-1;e=G.next[e]){
		int v=G.to[e];
		T capa=G.capa[e],flow=G.flow[e];

		if(capa-flow>ZERO && layer[v]>layer[u]){
			T w=augment(G,v,t,min(water,capa-flow));
			if(w>ZERO){
				G.flow[ e ]+=w;
				G.flow[e^1]-=w;
				return w;
			}
		}
	}
	return ZERO;
}

template<class T>
T Dinic(graph<T> &G,int s,int t){
	int n=G.n;
	T ans=ZERO;
	while(make_layer(G,s,t)){
		rep(u,n) now[u]=G.head[u];
		for(T water(51,1);water>ZERO;ans+=water) water=augment(G,s,t,INF);
	}
	return ans;
}

int main(){
	for(int n,m;scanf("%d%d",&n,&m),n;){
		graph<polynomial> G;
		G.init(n);
		rep(i,m){
			int u,v;
			char s[512]; scanf("%d%d%s",&u,&v,s); u--; v--;
			G.add_undirected_edge(u,v,parse(s));
		}
		print(Dinic(G,0,n-1));
	}
	return 0;
}

Measured memory_bytes: 1576