akhauriyash/Code-Regression huggingface dataset:
const MOD: u32 = 998244353;

fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut it = s.split_whitespace();
	let n: usize = it.next().unwrap().parse().unwrap();
	let s: u32 = it.next().unwrap().parse().unwrap();
	let a: Vec<u32> = it.take(n).map(|a| a.parse().unwrap()).collect();

	let mut dp = vec![0; s as usize + 1];
	dp[0] = 1;
	for &a in a.iter() {
		let mut next = vec![0; s as usize + 1];
		for si in 0..=s {
			next[si as usize] = (next[si as usize] + 2 * dp[si as usize]) % MOD;
			if si + a <= s {
				next[(si + a) as usize] = (next[(si + a) as usize] + dp[si as usize]) % MOD;
			}
		}
		dp = next;
	}
	println!("{}", dp[s as usize]);
}


Measured memory_bytes: 2168
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    long n, k; cin >> n >> k;
    long a[500], sum = 0; for(int i = 0; i < n; ++i) cin >> a[i], sum += a[i];

    vector<int> ps;
    for(int i = 1; i * i <= sum; ++i) {
        if(sum % i == 0) {
            ps.push_back(i);
            if(sum / i != i) ps.push_back(sum / i);
        }
    }
    sort(ps.rbegin(), ps.rend());

    for(int p : ps) {
        vector<long> s;

        for(int i = 0; i < n; ++i) s.push_back(a[i] % p);
        sort(s.begin(), s.end());
        
        int l = 0;
        long cnt = 0;
        for(int r = n - 1; r >= 0; --r) {
            if(s[r] % p == 0) continue;

            long diff = p - s[r];

            while(diff != 0) {
                long tmp = min(s[l], diff);

                diff -= tmp;
                cnt += tmp;
                s[l] -= tmp;
                if(s[l] == 0) ++l;
            }
        }

        if(cnt <= k) {
            cout << p << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */

    int a = sc.nextInt();
    int p = sc.nextInt();

    p += 3 * a;

    os.println(p/2);
  }
}

Measured memory_bytes: 22100
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }
template<typename T>
void put(std::string& buf, T const& ans) { buf += std::to_string(ans) + "\n"; }

int const MAXN = 3e5;
int const MAXA = 6.4e5;
int N, f[MAXN];

int main() {
  std::cin >> N;
  std::map<int,int> m;
  for(int i = 0; i < N; ++i) { int A; std::cin >> A; ++m[A]; }
  int n = 0;
  std::map<int,int> d;
  for(auto s: m) ++d[s.second];
  int sum = 0;
  for(int x = 0; x < N; ++x) {
    if(d.count(x) > 0) sum += x*d[x];
    f[x] = sum/(x+1);
  }
  sum = d[N];
  for(int x = N-1; x >= 0; --x) {
    f[x] += sum;
    if(d.count(x) > 0) sum += d[x];
  }
  
  std::string ans_s;
  ans_s.reserve(MAXA);
  int ans = N;
  for(int k = 1; k <= N; ++k) {
    ans = std::min(ans, N/k);
    while(ans > 0 && k > f[ans-1]) --ans;
    put(ans_s, ans);
  }
  fin(ans_s);
  return 0;
}


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

int main() {
    map<int, int> cnt;
    int x;
    while (scanf("%d", &x) != EOF) cnt[x]++;
    int m = 0;
    for (map<int, int>::iterator it = cnt.begin(); it != cnt.end(); ++it) {
        if (m < it->second) m = it->second;
    }
    for (map<int, int>::iterator it = cnt.begin(); it != cnt.end(); ++it) {
        if (m == it->second) printf("%d\n", it->first);
    }
    return 0;
}

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

// #include "../../template-proj/myMente.h"

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

#define MOD 1000000007
#define rp(i,n) for(int i=0;i<(n);i++)
#define up(i,s,e,d) for(int i=(s);i<(e);i+=(d))
#define ot(x) cout<<(x)
#define ote(x) cout<<(x)<<endl

int main(){
	int N,T;
	cin>>N>>T;
	vi start(N); rp(i,N)cin>>start[i];

	ll ans = 0;
	int s = 0;
	int e = T;
	up(i,1,N,1){
		if(e>=start[i]){
			ans += start[i]-s;
			s = start[i];
			e = s+T;
		}
		else{
			ans += T;
			s = start[i];
			e = s+T;
		}
	}
	ans+=T;
	ote(ans);
}


Measured memory_bytes: 1024
#include<iostream>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class question {
public:
	string s;
	vector<vector<int>> a;
	int ctoi(char c) {
		return (int)c - (int)'a';
	}
	void ans() {
		cin >> s;
		int n = s.size();
		a.resize(26, vector<int>(1, -1));
		REP(i, n) a[ctoi(s[i])].push_back(i);
		int res = n;
		REP(i, 26) {
			a[i].push_back(n);
			int k = a[i].size();
			int tmp = 0;
			for (int j = 1;j < k;j++) {
				tmp = max(tmp, a[i][j] - a[i][j - 1]-1);
			}
			res = min(res, tmp);
		}
		cout << res << "\n";
	}

};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	question q;
	q.ans();
	
	return 0;
}


Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.buffer.readline

    def gcd(x, y):
        if y == 0:
            return x
        while y != 0:
            x, y = y, x % y
        return x

    def lcm(x, y):
        return x*y//gcd(x, y)

    N, M = (int(i) for i in input().split())
    A = [int(i)//2 for i in input().split()]
    cnt = [0]*(N)
    for i, a in enumerate(A):
        while a % 2 == 0:
            cnt[i] += 1
            a //= 2
    if any(cnt[0] != c for c in cnt):
        return print(0)
    L = 1
    for a in A:
        L = lcm(L, a)

    ans = 0
    mul = 1
    while L*mul <= M:
        ans += 1
        mul += 2
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 58224
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n=parseInt(readline())
    data=sort([parseMap(split(readline())) for i in 1:n],by=x->x[3],rev=true)
    if n==1
        ans=join(data[1]," ")
    else
        ans="-1 -1 -1"
        for i in 0:100
            for j in 0:100
                flg=true
                dis=abs(data[1][1]-i)+abs(data[1][2]-j)
                hight=data[1][3]
                for (x,y,h) in data
                    if h>0 && abs(x-i)+abs(y-j)+h != dis+hight
                        flg=false
                    end
                end
                for (x,y,h) in data
                    if h!=max(dis+hight-abs(x-i)+-abs(y-j),0)
                        flg=false
                    end
                end
                if flg==true && dis+hight>0
                    ans="$i $j $(dis+hight)"
                    break
                end
            end
            if ans!="-1 -1 -1"
                break
            end
        end
    end
    println(ans)
end
main()

Measured memory_bytes: 118296
h,w = map(int,input().split())
S = [input() for i in range(h)]
for i in range(h):
    for j in range(w):
        if S[i][j] == '#' :
            print('#',end='')
            continue
        cnt = 0
        for dx in [-1,0,1]:
            for dy in [-1,0,1]:
                if not 0 <= i+dx < h or not 0 <= j+dy < w: continue
                if S[i+dx][j+dy] == '#' : cnt += 1
        print(cnt,end='')
    print()

Measured memory_bytes: 3444
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<string>
#include<set>
#include<utility>
#include<vector>
using namespace std;

int solve(){
  string s; cin >> s;
  int q;  cin >> q;
  bool rev = false;
  string head = "", tail = "";
  for(int i=0; i<q; ++i){
    int t;  cin >> t;
    if(t==1)  rev = !rev;
    if(t==2){
      int f;  char c; cin >> f >> c;
      if((f==1) == !rev){
        head += c;
      }
      else{
        tail += c;
      }
    }
  }
  if(!rev) {
    reverse(head.begin(), head.end());
    cout << head << s << tail << endl;
  }else{
    reverse(s.begin(), s.end());
    reverse(tail.begin(), tail.end());
    cout << tail << s << head << endl;
  }
  return 0;
}

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


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

typedef long long ll;

const int MN = 100010;

int N;
ll L[MN], R[MN], D[MN];
multiset<ll> le, ri;

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%lld %lld", &L[i], &R[i]);
        D[i] = R[i] - L[i];
    }

    le.insert(R[0]);
    ri.insert(R[0]);
    ll loffset = 0;
    ll roffset = 0;
    ll ans = 0;

    for(int i = 1; i < N; i++) {
        loffset -= D[i - 1];
        roffset += D[i];

        ll l = *le.rbegin() + loffset;
        ll r = *ri.begin() + roffset;

        if(r < R[i]) {
            ri.erase(ri.find(r - roffset));
            le.insert(r - loffset);
            ri.insert(R[i] - roffset);
            ri.insert(R[i] - roffset);
            ans += R[i] - r;
        }
        else if(R[i] < l) {
            le.erase(le.find(l - loffset));
            ri.insert(l - roffset);
            le.insert(R[i] - loffset);
            le.insert(R[i] - loffset);
            ans += l - R[i];
        }
        else {
            le.insert(R[i] - loffset);
            ri.insert(R[i] - roffset);
        }
    }

    printf("%lld", ans);
}


Measured memory_bytes: 12032
import sys
from operator import itemgetter

read = sys.stdin.read

N, *XL = map(int, read().split())

seq = [(X - L, X + L) for X, L in zip(*[iter(XL)] * 2)]
seq.sort(key=itemgetter(1))
answer = 0
left = -10 ** 10
for i, j in seq:
    if left <= i:
        answer += 1
        left = j

print(answer)


Measured memory_bytes: 27100
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;


const int MOD = 1e9 + 7;
int32_t main()
{
	IOS
	int n,m;cin>>n>>m;
	vector<string>s(n);
	for(int i=0;i<n;i++)
	cin>>s[i];
	vector<vector<int>>dp(n,vector<int>(m));
	dp[0][0]=1;
	for(int j=1;j<m;j++)
	if(s[0][j]!='#')dp[0][j]+=dp[0][j-1];
	for(int i=1;i<n;i++)
	if(s[i][0]!='#')dp[i][0]+=dp[i-1][0];
	
	for(int i=1;i<n;i++)
	for(int j=1;j<m;j++)
	{
		if(s[i][j]!='#')
		{
			dp[i][j]+=dp[i-1][j]+dp[i][j-1];
			dp[i][j]%=MOD;
		}
	}
	
	cout << dp[n-1][m-1] << endl;
	
	
	
	
}


Measured memory_bytes: 9216
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */
    int n = sc.nextInt();
    String s = sc.next();
    boolean[] b = new boolean[n];

    for (int i = 0 ; i < n; i++) {
      if (s.charAt(i) == '#') { // black
        b[i] = false;
      } else { // white
        b[i] = true;
      }
    }

    /* logic */

    // first target is all false.
    int count = 0;
    for (int i = 0; i < n; i++){
      if (b[i]) {
        count++;
      }
    }
    
    int answer = count;
    for (int i = 0; i < n; i++){
      // target is [0..i] is true, [i + 1..n - 1]  is false
      // i index should be true
      if (!b[i]) {
        count++;
      } else {
        count--;
      }
      answer = Math.min(answer, count);
    }
    os.print(answer);

  }
}

Measured memory_bytes: 28332
# -*- coding: utf-8 -*-

n, m = map(int, input().split())

ab = [list(map(int, input().split())) for i in range(n)]
cd = [list(map(int, input().split())) for i in range(m)]
tmp = 0

for i in range(len(ab)):
    mnh = 10**20
    for j in range(len(cd)):
        a, b = ab[i]
        c, d = cd[j]
        if mnh > abs(a-c) + abs(b-d):
            mnh = abs(a-c) + abs(b-d)
            tmp = j
    print(tmp+1)


Measured memory_bytes: 3064
// Problem : A - Takoyaki
// Contest : AtCoder - AtCoder Beginner Contest 176
// URL : https://atcoder.jp/contests/abc176/tasks/abc176_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;
const long long int  modu=1e9+7;
#define endl '\n'
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define inp(x)  for(auto &t:x) cin>>t;
#define itr     vector<int>::iterator
#define debug(a) cout << #a << "=" << a << ' '<<endl;
#define out(x)  for(auto &t:x) cout<<t<<" "; cout<<endl;
#define ff first
#define ss second
#define pb push_back
#define initialize(a,v)  for(int i=0;i<a.size();++i) a[i]=v;
#define all(x) x.begin(),x.end()
#define mpt(mp) for(auto it=mp.begin();it!=mp.end();it++)
#define trav(x) for(int i=0;i<(int)x.size();++i)
#define mkp(a,b) make_pair(a,b)
#define sz(x)  (int)x.size()

int noofdig(int N)
{
	return floor(log10(N))+1;
}


ll f(ll a)
{

return 0;

}



void pre()
{

}



void solve()
{

double n,x,t;
cin>>n>>x>>t;


// x pieces takes t minutes 

int d= ceil(n/x) *t;
//debug(d);

cout<<d<<endl;




}



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

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


Measured memory_bytes: 3612
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;




//   a/b mod c
ll moddiv(ll a,ll b){
	ll x0=MOD,x1=b,x2,n0=0LL,n1=1LL,n2,t=a%b,m,ans;
	if (t==0) return a/b;
		for(int i=0;i<900;i++){
      m=x0/x1;
      x2=x0-x1*m;
      n2=(n0-m*n1)%MOD;
      if (x2==1){
        ans=(n2+MOD)%MOD;
        break;
      }
      x0=x1;x1=x2;
      n0=n1;n1=n2;
    }
	return (a+((t*ans)%MOD)*b-t)/b;
}
//剰余の割ざん

//aのn乗 mod c
ll expmod(ll a,ll n){
  ll ans=1LL,aa=a,beki=n;
  for(int i=0;i<64;i++){
    if (beki%2==1) ans=ans*aa%MOD;
    aa=aa*aa%MOD;
    beki/=2;
    if (beki==0)break;
  }
  return ans;
}




int main(){
  ll ans=0;
  cin >> n ;
  vi a(n),b(1000000),aa(n);
  REP(i,n) cin>>a[i];
  REP(i,n) aa[i]=a[i];


// エラトステネスのふるい
    int MAX = 101010;
    vector<int> is_prime(MAX, 1);
    is_prime[0] = 0, is_prime[1] = 0;
    for (int i = 2; i < MAX; ++i) {
        if (!is_prime[i]) continue;
        for (int j = i*2; j < MAX; j += i) is_prime[j] = 0;
    }


  //ますは素因数
  ll so;
  int bj;
  ll bjnum;
  REP(i,n){
    for(int j=0;j<1000;j++){
      if (!is_prime[j]) continue;
      if (j*j>a[i])break;
      if (a[i]%j==0){
        bjnum=0;
        for(int k=0;k<55;k++){
          if (a[i]%j==0){
            bjnum++;
            a[i]/=j;
          }else{
            break;
          }
        }
        b[j]=max(b[j],bjnum);
        //cout<<j<<"!"<<bjnum<<endl;
      }
    }

    if (a[i]!=1){
      b[a[i]]=max(b[a[i]],1LL);
    }

  }


  ll saibai=1;
  

  REP(i,1000000){
    if (b[i]!=0){
      for(int j=0;j<b[i];j++){
        saibai=saibai*i%MOD;
      }
    }
  }

  //cout<<b[3]<<"!?"<<endl;

  //cout<<saibai<<endl;
  

  REP(i,n){
    ans+=moddiv(saibai,aa[i]);
    ans%=MOD;
    
  }




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






Measured memory_bytes: 8576
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <istream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <climits>
using namespace std;

typedef ostringstream OSS;
typedef istringstream ISS;

typedef vector<int> VI;
typedef vector< VI > VVI;

typedef long long LL;

typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define X first
#define Y second

const LL MOD = 1000000007;

template<typename T>
void dump(T a, int n) { for (int i = 0; i < n; i++) cout << a[i] << (i == n - 1 ? '\n' : ' '); }

template<typename T>
void dump(T a) { dump<T>(a, a.size()); }

VPII offset(VPII line) {
	int x0 = line[0].X, y0 = line[0].Y;
	for (int i = 0; i < (int)line.size(); i++) {
		line[i].X -= x0;
		line[i].Y -= y0;
	}

	return line;
}

VPII rotate90(VPII line) {
	for (auto &l : line) {
		swap(l.X, l.Y);
		l.X *= -1;
	}
	return line;
}

bool same(VPII &line1, VPII &line2) {
	if (line1.size() != line2.size()) {
		return false;
	}

	for (int i = 0; i < (int)line1.size(); i++) {
		if (line1[i] != line2[i]) {
			return false;
		}
	}

	return true;
}

bool some(vector< VPII > &lines0, VPII &line, VPII &rline) {
	for (int i = 0; i < 4; i++) {
		if (same(lines0[i], line) || same(lines0[i], rline)) {
			return true;
		}
	}
	
	return false;
}

int main(void) {
	for (int N; cin >> N, N;) {
		vector< VPII > lines0(4);
		vector< VPII > lines(N + 1);
		vector< VPII > rlines(N + 1);

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

			for (int j = 0; j < M; j++) {
				cin >> x >> y;
				lines[i].emplace_back(x, y);
			}
		}

		// reverse set
		for (int i = 0; i <= N; i++) {
			rlines[i] = VPII(lines[i].rbegin(), lines[i].rend());
		}

		// lines0 4dt set
		lines0[0] = lines[0];
		for (int i = 1; i < 4; i++) {
			lines0[i] = rotate90(lines0[i - 1]);
		}

		// offset
		transform(lines.begin(), lines.end(), lines.begin(), offset);
		transform(rlines.begin(), rlines.end(), rlines.begin(), offset);
		transform(lines0.begin(), lines0.end(), lines0.begin(), offset);

		// diff
		for (int i = 1; i <= N; i++) {
			if (some(lines0, lines[i], rlines[i])) {
				cout << i << endl;
			}
		}
		cout << "+++++" << endl;
	}

	return 0;
}

Measured memory_bytes: 1212
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int res = 0;
        for(int i = 1; i <= N; i++) {
            String s = String.valueOf(i);
            int len = s.length();
            if(len % 2 != 0) res++;
        }
        System.out.println(res);
    }
}


Measured memory_bytes: 40908
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  //b-aがbの添え字を与えるので1/2*(b-a)(b-a+1)-bが高さ
  cout << 1.0/2.0*(b-a)*(b-a+1)-b << endl;
}

Measured memory_bytes: 256
<?php
    fscanf(STDIN, '%d %d %d %d',$a,$b,$c,$k);

    if($k <= ($a+$b)){
        if($k <= $a){
            $ans = $k;
        }else{
            $ans = $a;
        }
    }else{
        $ans = $a - ($k-$a-$b);
    }
    
    echo $ans.PHP_EOL;

?>

Measured memory_bytes: 16204
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
using namespace std;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define mod 1000000007
#define PI 3.1415926535897932384626433
#define se second
#define fi first
#define pb push_back
#define T true
#define F false
#define endl "\n"
typedef char ch;
typedef bool boll;
typedef string st;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef set < string > sst;
typedef set < long long > sl;
typedef queue < long long > que;
typedef vector < long long > vec;
typedef map < long long, long long > mll;
typedef pair < long long, long long > pll;
typedef vector < pair < long long, long long > > vpl;
typedef pair < long long, unsigned long long > pul;

int main(){
    string s;
    cin >> s;
    if(s=="ARC") cout << "ABC";
    else cout << "ARC";
}


Measured memory_bytes: 3624
pub struct ProconReader<R: std::io::Read> {
    reader: R,
}

impl<R: std::io::Read> ProconReader<R> {
    pub fn new(reader: R) -> Self {
        Self { reader }
    }
    pub fn get<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&byte| byte == b' ' || byte == b'\n' || byte == b'\r')
            .take_while(|&byte| byte != b' ' && byte != b'\n' && byte != b'\r')
            .collect::<Vec<_>>();
        std::str::from_utf8(&buf)
            .unwrap()
            .parse()
            .ok()
            .expect("Parse Error.")
    }
}

fn z_algorithm<T: PartialEq>(a: &[T]) -> Vec<usize> {
    let n = a.len();
    let mut z = vec![0; n];
    z[0] = n;
    let mut i = 1;
    let mut len = 0;
    while i < n {
        while i + len < n && a[len] == a[i + len] {
            len += 1;
        }
        z[i] = len;
        if len == 0 {
            i += 1;
            continue;
        }
        let mut j = 1;
        while j + z[j] < len {
            z[i + j] = z[j];
            j += 1;
        }
        i += j;
        len -= j;
    }
    z
}

fn main() {
    let stdin = std::io::stdin();
    let mut rd = ProconReader::new(stdin.lock());

    let n: usize = rd.get();
    let s: String = rd.get();
    let s = s.chars().collect::<Vec<_>>();
    let mut ans = 0;
    for i in 0..n {
        let z = z_algorithm(&s[i..n]);
        for j in (i + 1)..n {
            ans = std::cmp::max(ans, std::cmp::min(j - i, z[j - i]));
        }
    }
    println!("{}", ans);
}

Measured memory_bytes: 2220
S = input()
n = [0]*(len(S)+1)

if S[0]=='<':
    n[0]==0
for i in range(0,len(S)):
    if S[i]=='>':
        n[i+1]=0
    else:
        n[i+1]=n[i]+1
        
for i in range(len(S)-1,-1,-1):
    if S[i]=='>':
        n[i]=max(n[i],n[i+1]+1)
        
print(sum(n))

Measured memory_bytes: 28916
import math
n=int(input())
s=0
for i in range(n):
    a=int(input())
    b=math.ceil(a**0.5)
    if a==2:
        s+=1
    elif a%2==0 or a < 2:
        continue
    else:
        c=0
        for j in range(3,b+1,2):
            if a%j==0:
                c+=1
                break
        if c==0:
            s+=1
print(s)


Measured memory_bytes: 5768
from collections import Counter
N , K = map(int,input().split())
an= list(map(int,input().split()))
ac = Counter(an)
la = list(ac.items())
la.sort(key=lambda x:x[1])
ans = 0
if len(la) <= K:
    print(0)
else:
    for i in range(len(la)-K):
        ans += la[i][1]
    print(ans)

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

//Function Macros:
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

//Type Definitions:
typedef long long ll;
typedef unsigned long long ull;

//Constants:
const int INF = 2e9;
const int MOD = 1e9 + 7;

//Global Variables:

//Prototype Declarations:
int gcd(int, int);

//================ Main Loop ================
int main() {
    int n, q;
    cin >> n >> q;
    queue<pair<string, int>> v;
    string s;
    int t, now = 0;
    rep(i, n) {
        cin >> s >> t;
        v.push(make_pair(s, t));
    }

    while(!v.empty()) {
        pair<string, int> p;
        p = v.front();
        v.pop();
        if(p.second <= q) {
            now += p.second;
            cout << p.first << " " << now << endl;
        } else {
            now += q;
            p.second -= q;
            v.push(p);
        }
    }
    return 0;
}
//===========================================

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


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

int main() {
  int n,l; 
  int min = 101;
  int sum =0;
  cin >> n;
  cin >> l;
  vector<int> vec(n);
  for (int i = 0; i < n; i++) {
  	vec.at(i)=i+l;
	}
  for(int i=0;i<n;i++){
    sum+=vec.at(i);
    if(vec.at(i)==0){
      min=0;
    }
    if(abs(vec.at(i))<=abs(min)){
      min = vec.at(i);
    }
  }
  cout << sum-min<<endl;
}



Measured memory_bytes: 256
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
input = sys.stdin.readline


N = int(input())

d2 = [1]
inverse = [0, 1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)
for i in range( 2,  10):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

G = [[] for _ in range(N+1)]
for v in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
r = N*d2[N-1]-N-r
for _ in range(N):
    r = r*500000004 % mod
print(r)


Measured memory_bytes: 196016
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <math.h>
#include <string>
#include <stack>
#include <stdlib.h>
#include <iomanip>
#include <queue>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define mset(a, b) memset(a, b, sizeof(a))
#define LL long long
#define P pair<int, int>
#define PLL pair<LL, LL>
const int MAX = 1e5 + 5;
const int inf = 0x3f3f3f3f;
using namespace std;

LL n, x;
vector<LL> cnt_L;
vector<LL> cnt_P;
LL solve(LL x, LL n)
{
    if(x == 0)  return 0;
    if(x == cnt_L[n]){
        return cnt_P[n];
    }
    LL p = (cnt_L[n]+1) >> 1;
    if(x < p){
        return solve(x-1, n-1);
    }
    else if(x > p)
    {
        return cnt_P[n-1] + solve(x-p, n-1) + 1LL;
    }
    else{
        return cnt_P[n-1]+1;
    }
}
int main()
{
    cin >> n >> x;
    cnt_L.resize(n+1);
    cnt_P.resize(n+1);
    cnt_L[0] = 1;
    cnt_P[0] = 1;
    for(int i = 1; i <= n; i++){
        cnt_L[i] = cnt_L[i-1]*2 + 3;
        cnt_P[i] = cnt_P[i-1]*2 + 1;
    }
    cout  << solve(x, n) << endl;
    return 0;
}



Measured memory_bytes: 256
/*
  AUTHOR:SOURABH
  CREATED:22:07:19
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<pair<int, int> , null_type, less< pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define W while
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(it,s) for(it=s.begin();it!=s.end();it++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mod 1000000007
#define MAX 100005
#define M 32

using namespace std;
using namespace __gnu_pbds;

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

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    ll n,m,ans=0,sum=1;
    cin>>n>>m;
    while(sum<m)
    {
        sum=(sum-1)+n;
        ans++;
    }
    cout<<ans;
    return 0;
}





















Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define substr(s,f,t) (s.substr(f-1,t-f+1))
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{int x,y,t;};
struct Edge{int to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=1010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(int from,int to,int cost){E[from-1].pb({to-1,cost});}
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;cin>>n;
  vi ans;
  ans.pb(ceil((double)((double)(sqrt(1+8*n)-1)/2)));
  int no=n-ans[0];
  for(int i=ans[0]-1;i>=1;i--){
    if(i<=no){
      no-=i;
      ans.pb(i);
    }
  }
  for(int i=ans.size()-1;i>=0;i--)
    cout<<ans[i]<<endl;
  return 0;
}


Measured memory_bytes: 384
import heapq
N,M=map(int,input().split())
A=list(map(int,input().split()))
heapq.heapify(A)
numbers=[]
for _ in range(M):
    B,C=map(int,input().split())
    numbers.append([C,B])
numbers=sorted(numbers,reverse=True)
for number in numbers:
    B=number[1]
    C=number[0]
    for _ in range(B):
        a = heapq.heappop(A)
        if C <= a:
            heapq.heappush(A, a)
            break
        else:
            heapq.heappush(A,C)
print(sum(A))


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

int main() {
    int n;
    cin >> n;
    map<int, int> m;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        m[a]++;
    }

    long long side1 = -1, side2 = -1;
    for (auto i = m.begin(); i != m.end(); i++) {
        if (i -> second >= 2) {
            if (i -> first > side1) {
                side2 = side1;
                side1 = i -> first;
                
                if (i -> second >= 4 && i -> first > side2) side2 = i -> first;
            }
            else if (i -> first > side2) side2 = i -> first;
        }
    }

    if (side1 == -1 || side2 == -1) {
        cout << 0 << endl;
        return 0;
    }

    cout << side1 * side2 << endl;
}

Measured memory_bytes: 4992
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#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>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int a[210][3];
signed main() {
    int N; cin >> N;
    for(int i=0; i<N; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }

    vector<int> ans(N);
    for(int x=0; x<3; x++) {
        for(int i=0; i<N; i++) {
            bool dbl = false;
            for(int j=0; j<N; j++) {
                if(i == j) continue;
                if(a[i][x] == a[j][x]) dbl = true;
            }
            if(!dbl) ans[i] += a[i][x];
        }
    }

    for(int i=0; i<N; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}



Measured memory_bytes: 3104
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int K = sc.nextInt();
		sc.close();
		for(int i=0;i<K;++i){
			if(A >= B){
				B *= 2;
			}else{
				C *= 2;
			}

		}
		if(B > A && C > B){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}


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

using namespace std;using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


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

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

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

int main() {
  int64 A, B, C, D;
  cin >> A >> B >> C >> D;
  --A;
  int64 add = 0;
  add += B / C;
  add -= A / C;
  add += B / D;
  add -= A / D;
  C = C / __gcd(C, D) * D;
  add -= B / C;
  add += A / C;
  cout << (B - A) - add << endl;
}






Measured memory_bytes: 256
import java.util.*;
public class Main {
public static void main(String[] args){
    Scanner s=new Scanner(System.in);
    String S1=s.next();
    String S2=s.next();

    char[] t=new char[3];
    char[] t2=new char[3];
    int ans=0;
    for(int i=0;i<3;i++){
       t[i]=S1.charAt(i);
    }
    for(int i=0;i<3;i++){
        t2[i]=S2.charAt(i);
    }
    for(int i=0;i<3;i++){
        if(t[i]==t2[i]){
            ans++;
        }
    }
    System.out.println(ans);
}
}

Measured memory_bytes: 21716
n = int(input())
x = list(map(int, input().split()))
xsort = sorted(x)

n1, n2 = xsort[n//2-1], xsort[n//2]

for i in range(n):
    if x[i]  <= n1:
        print(n2)
    else:
        print(n1)

Measured memory_bytes: 25228
#include<bits/stdc++.h>
 
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,a,b)    for(int i=a;i<b;i++)
#define repn(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define mp  make_pair
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
 
using namespace std;

int i,j,k;
 
int max(int a, int b)
{
    if(a>b) return a;
    else return b;
}
 
int min(int a,int b)
{
    if(a<b) return a;
    else return b;
}

int fast_power(int a,int b)
{
    int res=1;
    while(b>0)
    {
        if(b%2==0)
        {
            b/=2;
            a=(a*a)%mod;
        }
        else
        {
             b/=2;
             res=(res*a)%mod;
            a=(a*a)%mod;
        }
    }
    return res;
}
int palindrone(string s,int l,int r)
{
    int flag=1;
    while(l<r)
    {
        if(s[l]!=s[r])
        {
            flag=0; 
            break;
        }
        l++;
        r--;
    }
    return flag;
}

signed main()
{
    IOS;
    double l;
    cin>>l;
    double ans=(l*l*l)/27;
    cout<<fixed<<setprecision(9)<<ans;
    return 0;
}

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

using namespace std;
using ll = long long;

void init();
void solve();

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__ "Yes"
#define FALSE__ "No"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a;
#define lcoutln(a) cout << a << endl;
#define lcerr(a) cerr << a;
#define lcerrln(a) cerr << a << endl;
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
#define MOD 1000000007

signed main()
{
	init();
	solve();
}

int N, M;
int A[101000];

void init()
{
	cin >> N;
	M = N / 2;
	rep(i, N) cin >> A[i];
	sort(A, A+N);
}


int culc()
{
	ll res = 1;
	rep(i, M) {
		res = res * 2 % MOD;
	}
	return (int) res;
}



void solve()
{
	if (N % 2 == 1) {
		if (A[0] != 0) {
			cout << 0 << endl;
			return;
		}
		int pos = 0;
		reps(i, 1, M+1) {
			rep(j, 2) {
				pos++;
				if (A[pos] != 2 * i) {
					cout << 0 << endl;
					return;
				}
			}
		}
		cout << culc() << endl;
	} else {
		int pos = -1;
		rep(i, M) {
			rep(j, 2) {
				pos++;
				if (A[pos] != 2 * i + 1) {
					cout << 0 << endl;
					return;
				}
			}
		}
		cout << culc() << endl;
	}
}



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

int main(){
    int n;
	cin >> n;
	vector<int> order(n, 0);
	for(int i=1; i<=n; i++){
		int already_in;
		cin >> already_in;
		order[already_in-1]=i;
	}
	for(int i=0; i<n; i++){
		cout << order[i] << " ";
	}
    return 0;
}

Measured memory_bytes: 1152
n = int(input())
num_list = list(map(int, input().split()))
count = 0
b=0
c=0
a=0


for i in num_list:
  a = i
  for j in num_list:
    if j != a:
      b = j
      for k in num_list:
        if k != a and k != b : 
          c = k    
          if a + b > c and b + c > a and a + c > b :
            count = count + 1
        else:
          continue
    else:
      continue 
      
print(int(count/6))

Measured memory_bytes: 9132
from collections import defaultdict
from bisect import bisect_left

S = input()
T = input()

SS = S + S
lens = len(S)

index = defaultdict(list) # alphabet to indices

for i, ss in enumerate(SS):
    index[ss].append(i)

x = -1 
for t in T:
    arr = index[t]
    if len(arr) == 0:
        x = -2
        break
    y = (x + 1) % lens
    i = bisect_left(arr, y)
#    print(arr, i, y)
    x = (x + 1) + arr[i] - y
    
answer = x + 1
print(answer)


Measured memory_bytes: 12404
from decimal import Decimal

n = int(input())
x = list(map(int, input().split()))

y = x.copy()

y.sort()

m1 = y[n//2]
m2 = y[n//2 - 1]
m = Decimal(m1 + m2) / Decimal(2) 
#print(m1, m2)

for z in x:
    if z <= m:
        print(m1)
    else:
        print(m2)

Measured memory_bytes: 33304
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
#define uni(q) unique(all(q)),q.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

int main(){
    string s; cin >> s;
    ll n = s.size();
    vl alpha(26,0);
    rep(i,26){
        char c = 'a' + i;
        ll mx = 0;
        ll cnt = 0;
        rep(i,n){
            if(s[i] == c) {
                mx = max(mx,cnt);
                cnt = 0;
            }
            else cnt++;
        }
        mx = max(mx,cnt);
        alpha[i] = mx;
    }
    ll ans = INF;
    rep(i,26) ans = min(ans,alpha[i]);
    cout << ans << endl;
}


Measured memory_bytes: 256
K = int(input())
lunlun = []

for i in range(1,10):
    lunlun.append(i)
for i in lunlun:
    if len(lunlun)>K:
        break
    x = i % 10
    for j in range(max(0,x-1), min(x+2,10)):
        lunlun.append(i*10+j)
 
print(lunlun[K-1])

Measured memory_bytes: 7320
#include <iostream>
#include <list> //???????????????????????????
#include <vector>//????????¢??????????????????
#include <climits>
using namespace std;


bool solve(int i, int m , vector <int> &A){
	if (m == 0){
		return true;
	}
	
	int n= A.size();
	
	if (i >= n){
		return false;
	}
	
	bool res = solve(i + 1, m, A) || solve(i + 1, m - A[i], A);
	return res;

}

int main(void){
	std::cin.tie(0); 
	std::ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector <int> A(n);
	for(int i=0 ; i < n; i++){
		cin >> A[i];
	}
	int q;
	cin >> q;
	vector <int> mi(q);
	for(int i=0 ; i < q; i++){
		cin >> mi[i];
	}
	for(int j =0 ; j < q ; j++){
		
		if(solve(0,mi[j],A)){
			cout << "yes" << endl;
		}else cout << "no" << endl;
	}
		
	

}

Measured memory_bytes: 1188
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
#define reg register
#define fi first
#define se second
const int mod=1e9+7;
int n,m,f[301][301][301];
struct data{
	int l,cnt,nxt;
	data():l(0),cnt(0),nxt(0){}
	data(int l,int cnt,int nxt):l(l),cnt(cnt),nxt(nxt){}
}g[301];
int h[301],cntg;
inline void ins(int a,int b,int c){g[++cntg]=data(a,c,h[b]);h[b]=cntg;}
inline bool check(int x,int y,int z){
	reg int t=max(max(x,y),z);
	for(reg int i=h[t],cnt=0;i;i=g[i].nxt,cnt=0){
		if(g[i].l<=x)cnt++;
		if(g[i].l<=y)cnt++;
		if(g[i].l<=z)cnt++;
		if(g[i].cnt!=cnt)return 0;
	}
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);reg ll ans=0;f[0][0][0]=1;
	for(reg int i=1,a,b,c;i<=m;i++){scanf("%d%d%d",&a,&b,&c);ins(a,b,c);}
	for(reg int i=0;i<=n;i++)
		for(reg int j=0;j<=n;j++)
			for(reg int k=0;k<=n;k++){
				if(!f[i][j][k])continue;if(!check(i,j,k)){f[i][j][k]=0;continue;}
				reg int t=max(max(i,j),k);
				if(t==n){ans=(ans+f[i][j][k])%mod;continue;}
				f[t+1][j][k]=(1ll*f[t+1][j][k]%mod+f[i][j][k])%mod;
				f[i][t+1][k]=(1ll*f[i][t+1][k]%mod+f[i][j][k])%mod;
				f[i][j][t+1]=(1ll*f[i][j][t+1]%mod+f[i][j][k])%mod;
			}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 106752
<?php
list($N, $C) = ints();
for ($i = 0; $i < $C; ++$i) $D[] = ints();
for ($i = 0; $i < $N; ++$i) {
    $c[] = ints();
    for ($j = 0; $j < $N; ++$j) --$c[$i][$j];
}
echo dfs();
function dfs($d = 0, $selected = [])
{
    global $C;
    if ($d === 3) return calcD(array_keys($selected));
    for ($i = 0; $i < $C; ++$i) {
        if (isset($selected[$i])) continue;
        $_selected = $selected;
        $_selected[$i] = true;
        $res[] = dfs($d + 1, $_selected);
    }
    return min($res);
}
function calcD($a)
{
    global $memo;
    $res = 0;
    for ($i = 0; $i < 3; ++$i) {
        if (!isset($memo[$i][$a[$i]])) $memo[$i][$a[$i]] = subCalcD($i, $a[$i]);
        $res += $memo[$i][$a[$i]];
    }
    return $res;
}
function subCalcD($x, $to)
{
    global $N, $D, $c;
    $res = 0;
    for ($i = 0; $i < $N; ++$i) {
        for ($j = ($x + 2 * $i) % 3; $j < $N; $j += 3) {
            $from = $c[$i][$j];
            $res += $D[$from][$to];
        }
    }
    return $res;
}
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 24112
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm> // sort
#include <iomanip>
#include <queue>
#include <map>
#include <bits/stdc++.h>


using namespace std;

#define DEBUG 0
#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll INF = 1000000000000000000LL;
typedef pair<int,int> pint;


const int MOD = 1000000007;

//1,2,3,4
//
//1,2
//1,2,3
//1,2,3,4
//2,3
//2,3,4
//3,4

int main(){

#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    string res;
    int n;
    cin >> n;
    string s;
    cin >> s;

    ll lcnt = 0;
    ll rcnt = 0;
    ll l = 0;; 


    REP(i,s.size())
    {
        if(s[i] == '(')++lcnt;
        else
        {
            //現時点で足りなければ足す
            ++rcnt;
            if(rcnt > lcnt)
            {
                ++l;
                ++lcnt;
            }
        }

    }


    res = string(l, '(') + s + string(lcnt - rcnt, ')');

    cout << res << endl;

    return 0;     
}



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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

bool comp(P p1, P p2){
	return p1.second < p2.second;
}

int main(){
	int n;
	cin >> n;
	vector<int> a[200001];
	REP(i, n){
		int x;
		cin >> x;
		a[x].pb(i);
	}
	vector<P> f;
	REP(i, 200001){
		if(a[i].size() >= 2){
			REP(j, a[i].size()-1){
				if(a[i][j+1]-a[i][j] > 1) f.pb({a[i][j], a[i][j+1]});
			}
		}
	}
	sort(ALL(f), comp);
	int fs = f.size();
	ll dp[fs+1];
	dp[0] = 1;
	REP(i, fs){
		if(f[i].first < f[0].second) dp[i+1] = (dp[i]+1)%INF;
		else{
			int ft = 0, l = fs;
			while(l-ft>1){
				int m = (l+ft)/2;
				if(f[i].first >= f[m].second) ft = m;
				else l = m;
			}
			dp[i+1] = (dp[i] + dp[ft+1])%INF;
		}
	}
	cout << dp[fs] << endl;
	return 0;
} 


Measured memory_bytes: 12024
# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = input_int()
    s = set([input() for i in range(n)])

    print(len(s))


if __name__ == "__main__":
    main()


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

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  
  string o, e;
  cin >> o >> e;
  int ol = o.size();
  int el = e.size();
  
  string s = "";
  int lpcnt = 0;
  while(ol-1 >= lpcnt) {
    s.push_back(o[lpcnt]);
    if(el-1 >= lpcnt) {
      s.push_back(e[lpcnt]);
    }
    lpcnt++;
  }
  
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>

using namespace std;

#define int long long

signed main() {
	string S;
	cin >> S;
	for (int i = 0; i < S.length(); i++) {
		if (S[i] == ',')cout << " ";
		else cout << S[i];
	}
	cout << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
using pii = pair<int, int>;
using Graph = vector<vector<int>>;
int n, m;
Graph G;

bool visited[1001000];
vector<int> v;

void dfs(int u) {
  if (visited[u]) return;
  visited[u] = true;
  for (int i : G[u]) dfs(i);
  v.push_back(u);
}

void tsort() {
  for (int i = 0; i < n; i++) {
    dfs(i);
  }
  reverse(v.begin(), v.end());
}

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

  G.resize(n);

  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
  }
  tsort();
  reverse(v.begin(), v.end());

  int dp[n] = {};
  int ans = 0;
  for (int i : v) {
    for (int u : G[i]) {
      dp[i] = max(dp[i], dp[u] + 1);
    }
    ans = max(ans, dp[i]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 11424